Dọc theo con đường tơ lụa những con lạc đà cần mẫn chuyên chở tơ lụa, hương liệu và ngọc ngà đá quý của phương đông. Đá quý được phân thành 26 loại ký hiệu bằng chữ cái la tinh thường từ a đến z. Các lái buôn muốn bán được hàng với giá càng cao càng tốt. Trong chuyến đi này một lái buôn mang theo bộ đá quý gồm n viên. Ông xâu tất cả thành chuỗi và bày ra trên thảm trước một lãnh chúa hùng mạnh. Vị lãnh chúa cân nhắc đánh giá chất lượng bộ đá quý để quyết định có nên mua hay không. Theo quy tắc truyền thống của địa phương, giá trị của chuỗi ngọc phụ thuộc vào sự xuất hiện các cặp ngọc (~a_i~, ~b_i~), tức là phải có ngọc loại ~a_i~ đứng trước loại ~b_i~ ~(i = 1 ... k)~. Nếu giá trị chuỗi ngọc đủ lớn, lãnh chúa sẽ mua toàn bộ chuỗi ngọc.

Yêu cầu: Cho biết n và xâu S thể hiện các loại ngọc trong chuỗi, cách định giá trị chuỗi ngọc của địa phương. Hãy xác định giá trị của chuỗi ngọc.

Dữ liệu:

• Dòng thứ nhất chứa số nguyên dương T, là số lượng test có trong file dữ liệu
• Mỗi test có cấu trúc như sau:
  • Dòng thứ nhất chứa hai số nguyên dương n, k.
  • Dòng thứ 2 chứa xâu S.
  • Mỗi dòng trong k dòng sau chứa xâu 2 ký tự xác định cặp có giá trị.

Kết quả: Ghi ra một số nguyên – giá trị chuỗi ngọc

Ví dụ:

Input

1
7 3
abacaba
ab
ac
bb

Output

7

* Giới hạn:* 0 < T ≤ 10; 0 < n ≤ ~10^5~; 1 ≤ k ≤ ~10^5~.

* Ràng buộc:*

• Subtask1: 50% số test ứng với 50% số điểm của bài có n ≤ ~10^3~; k ≤ ~10^3~.
• Subtask2: 20% số test khác ứng với 20% số điểm của bài có n ≤ ~10^3~; k ≤ ~10^5~
• Subtask3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì.

Mê cung có ~n~ phòng đánh số từ 1 đến ~n~, được nối với nhau bởi ~m~ đoạn đường đi 2 chiều nối trực tiếp 2 phòng, đường đi thứ i có màu ~c_i~. Giữa 2 phòng có thể có nhiều đường đi nối trực tiếp. Đường đi trực tiếp có thể nối một phòng với chính nó. Người chơi được máy bay lên thẳng thả xuống phòng 1 và phải tìm đường đi tới phòng n. Độ dài của đường đi được tính bằng số đoạn đường nối giữa 2 phòng đã đi qua. Ai có đường đi ngắn nhất sẽ thắng cuộc. Nếu có nhiều người cùng có đường đi ngắn nhất thì so sánh theo thứ tự từ điển các màu đã đi qua. Người có đường đi ngắn nhất với thứ tự từ điển nhỏ nhất sẽ thắng. Đường đi lý tưởng là đường ngắn nhất và có thứ tự từ điển nhỏ nhất.

Dãy ~a~ = (~a_1~, ~a_2~, …, ~a_k~) được gọi là dãy có thứ tự từ điển nhỏ hơn dãy ~b~ = (~b_1~, ~b_2~, …, ~b_k~) nếu thỏa mãn:

• ~i – 1~ phần tử đầu tiên của hai dãy bằng nhau, tức là ~a_1~ = ~b_1~,~a_2~ = ~b_2~,....,~a_{i-1}~ = ~b_{i-1}~
• Phần tử thứ ~i~ của dãy ~a~ nhỏ hơn phần tử thứ ~i~ của dãy ~b~, tức là ~a_i~ < ~b_i~.

Ví dụ: dãy ~a~ = (1, 4, 5, 3, 6, 2, 3) có thứ tự từ điển nhỏ hơn dãy ~b~ = (1, 4, 5, 4, 1, 1, 2) vì 3 phần tử đầu tiên của dãy ~a~ bằng 3 phần tử đầu tiên của dãy ~b~ và phần tử thứ 4 của dãy ~a~ nhỏ hơn phần tử thứ 4 của dãy ~b~.

Yêu cầu: Cho ~m, n~ và các đường đi ~(u, v, c)~ xác định đường màu ~c~ nối từ phòng ~u~ tới phòng ~v~. Dữ liệu đảm bảo có đường đi từ phòng 1 đến phòng ~n~. Hãy xác định đường đi lý tưởng: số đoạn đường và màu của các đoạn đó theo trình tự đi.

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~,
• Dòng thứ ~i~ trong ~m~ dòng sau chứa 3 số nguyên ~u~, ~v~ và ~c~.

*Kết quả: *

• Dòng đầu tiên chứa số nguyên ~k~,
• Dòng thứ 2 chứa ~k~ số nguyên – màu của các đoạn theo trình tự đi.

Ví dụ:

Input

4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

Output

2
1 3

*Giới hạn: * 2 ≤ n ≤ ~10^5~,1 ≤ m ≤ 2×~10^5~,1 ≤ u, v ≤ n, 1 ≤ c ≤ ~10^9~

Ràng buộc:

• Subtask1: 30% số test ứng với 30% số điểm của bài tất cả các đường đi đều có cùng một màu.
• Subtask2: 30% số test khác ứng với 30% số điểm của bài có 1 ≤ c ≤ 9, 2 ≤ n ≤ ~10^2~ và 1 ≤ m ≤ ~10^3~.
• Subtask3: 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì.

Cho dãy số nguyên ~a_1~, ~a_2~, …, ~a_n~. Một dãy con là dãy được lập từ dãy đã cho bằng cách giữ lại một đoạn liên tiếp các số cạnh nhau. Giá trị của một dãy được tính bằng giá trị của phần tử lớn nhất trong dãy.

Yêu cầu: Với mỗi truy vấn dạng ~L, R~ hãy đếm xem có bao nhiêu dãy con của dãy đã cho có giá trị nằm trong đoạn ~[L, R]~.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~n~
• Dòng thứ hai chứa n số nguyên dương ~a_1~, ~a_2~, …, ~a_n~
• Dòng thứ ba ghi số nguyên dương ~m~ là số lượng truy vấn
• m dòng cuối cùng, mỗi dòng chứa hai số nguyên ~L, R~.

Kết quả: Gồm ~m~ dòng, mỗi dòng ghi kết quả một truy vấn theo thứ tự xuất hiện trong file dữ liệu.

Ví dụ:

Input

3
1 2 3
3
1 2
2 3
3 3

Output

3
5
3

Giới hạn: 1 ≤ n, m ≤ ~10^5~; 0 <~a_1~, ~a_2~, …, ~a_n~ ≤ ~10^9~; 1 ≤ L ≤ R ≤ ~10^9~.

Ràng buộc:

• Subtask1: 40% số test ứng 40% số điểm của bài có n, m ≤ ~10^2~.
• Subtask2: 30% số test khác ứng 30% số điểm của bài có n, m ≤ ~10^3~
• Subtask3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì.

Một quốc gia nọ có ~N~ thành phố. Người ta đã xây dựng ~M~ con đường một chiều để di chuyển giữa các thành phố. Quốc vương muốn đảm bảo rằng giữa hai thành phố bất kỳ, phải luôn tồn tại một cách di chuyển (trực tiếp hoặc gián tiếp) từ thành phố này đến thành phố kia. Bạn hãy kiểm tra xem ông có cần phải xây dựng các con đường mới không?

Dữ liệu vào:

• Dòng một chứa số nguyên dương ~T\ (T \leq 5)~ là số lượng quốc gia bạn cần giúp đỡ.
• Tiếp theo là ~T~ bộ dữ liệu, mỗi bộ dữ liệu gồm:
• Dòng đầu chứa ~2~ số nguyên ~N, M~, số thành phố và số con đường ~1~ chiều
• Mỗi dòng trong ~M~ dòng tiếp theo gồm ~2~ số nguyên ~u, v\ (1 \leq u, v \leq n,\ u \neq v)~: người ta đã xây dựng con đường ~1~ chiều từ ~u~ đến ~v~.

Dữ liệu ra:

Mỗi dòng là câu trả lời cho một bộ dữ liệu tương ứng: in ra YES nếu quốc vương cần xây thêm đường mới, NO nếu những con đường hiện tại đã thỏa mãn yêu cầu của ông.

Ví dụ:

Input:

2
3 3
1 2
2 3
3 1
3 2
1 2
2 3

Output:

NO
YES

Ràng buộc:

• Có ~40 \%~ điểm tương ứng với trường hợp ~N, M \leq 2000~.
• Có ~60 \%~ điểm tương ứng với trường hợp ~N, M \leq 100000~.

Giải thích:

Trong bộ dữ liệu thứ hai, có ~2~ con đường ~1 \rightarrow 2~ và ~2 \rightarrow 3~. Người ta không thể di chuyển từ thành phố ~3~ đến thành phố ~1~ với hai con đường này.