Cho một đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh. Một đỉnh hoặc cạnh được coi là loại bỏ được nếu bỏ đi đỉnh/cạnh đó không làm tăng số miền liên thông của đồ thị.

Yêu cầu

Hãy đếm số đỉnh và cạnh không nên bị loại bỏ.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N, M~ lần lượt là số đỉnh và số cạnh của đồ thị (~1 \leq N \leq 10^4~, ~1 \leq M \leq 5\cdot 10^4~). Các đỉnh được đánh số từ ~1~ đến ~N~.
• ~M~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u, v~ thể hiện cặp cạnh ~(u, v)~ của đồ thị (~1 \leq u, v \leq n~).

Kết quả

• Một dòng duy nhất chứa hai số nguyên lần lượt là số đỉnh và số cạnh không nên bị loại bỏ của đồ thị.

Ví dụ

Input

10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7

Output

4 3

Giải thích

• Các đỉnh mà ta không nên loại bỏ là: 10, 7, 3, 2.
• Các cạnh mà ta không nên loại bỏ nối các cặp đỉnh: (1, 10), (10, 2), (10, 3).

Trong phòng thi Tin học trẻ, Huy gặp một bài toán rất khó nhưng không muốn trở thành gánh nặng của đồng đội nên cần sự trợ giúp của bạn.

Cho đồ thị có hướng gồm ~N~ đỉnh, ~M~ cạnh có trọng số và ~K~ yêu cầu, mỗi yêu cầu có dạng ~(u,v)~. Mảng ~c~ gồm ~K~ phần tử nhận giá trị ~c_i = cost(u_i,v_i)~ (~1 \leq i \leq K)~ với ~cost(u_i, v_i)~ được định nghĩa là trọng số lớn nhất của cạnh trên một đường đi bất kỳ từ ~u~ tới ~v~. Lưu ý với một cặp ~(u, v)~ cố định, ~cost(u, v)~ có thể nhận nhiều giá trị khác nhau tùy thuộc vào đường đi được chọn.

Yêu cầu

~K~ yêu cầu, yêu cầu thứ ~i~ có dạng ~(u_i, v_i)~: hãy chọn ra đường đi tối ưu từ ~u_i \rightarrow v_i~ (~\forall i: 1 \leq i \leq K~) sao cho giá trị tối đa của mảng ~c~ đạt nhỏ nhất. Nói cách khác, hãy tối thiểu hóa giá trị ~\max(cost(u_i, v_i))~ (~\forall i: 1 \leq i \leq K~).

Dữ liệu

• Dòng đầu gồm ba số nguyên dương ~N~, ~M~, ~K~ ~(2 \leq N \leq 2 \times 10 ^ 4;\ M,\ K \leq 10 ^ 5)~.
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo mỗi dòng chứa ba số nguyên dương ~a_i,b_i,w_i~: có cạnh một chiều giữa hai đỉnh ~a_i,\ b_i~ và trọng số là ~w_i~ ~(1 \leq a_i, b_i \leq n,1 \leq w_i \leq 10^9)~.
• Dòng thứ ~i~ trong ~K~ dòng tiếp theo mỗi dòng có hai giá trị ~u_i,v_i\ (u_i \neq v_i)~ yêu cầu bạn gán ~c_i~ = ~cost(u_i,v_i)~ (~1 \leq u, v \leq n~). Nếu tồn tại ~i~ sao cho không có đường đi từ ~u_i~ đến ~v_i~, đáp án của toàn bộ bài toán sẽ là ~-1~.

Kết quả

• Một dòng duy nhất gồm giá trị nhỏ nhất có thể của ~max(c_i)~ (~\forall i: 1 \leq i \leq K)~.

Ví dụ

Input

4 5 3 
1 2 4 
2 3 2 
3 1 3 
4 3 5  
4 1 8 
3 2  
4 2 
2 1 

Output

5

Giải thích

• Với yêu cầu thứ nhất ~c_1~ = ~4~ ~(3 \rightarrow 1 \rightarrow\ 2)~.
• Với yêu cầu thứ hai ~c_2~ = ~5~ ~(4 \rightarrow 3 \rightarrow 1 \rightarrow 2)~.
• Với yêu cầu thứ ba ~c_3~ = ~3~ ~(2 \rightarrow 3 \rightarrow 1)~.

Một hệ thống gồm ~n~ máy tính đánh số từ ~1~ tới ~n~ được kết nối thành một mạng liên thông bởi ~m~ đoạn cáp, đánh số từ 1 tới ~m~. Đoạn cáp mạng thứ i kết nối 2 máy ~u_i~, ~v_i~ cho phép truyền dữ liệu 2 chiều giữa 2 máy này. Ngoài ra giữa 2 máy bất kì chỉ có tối đa 1 cáp nối và không có máy nào được nối với chính nó.

Một dãy các máy ~x_1, x_2, ..., x_p,~ trong đó giữa 2 máy ~x_j~ và ~x_{j+1}~ ~(j = 1, 2, ..., p - 1)~ có đoạn cáp nối, được gọi là một đường truyền tin từ máy ~x_1~ tới máy ~x_p~. Đoạn cáp nối máy ~u~ và ~v~ gọi là xung yếu nếu loại bỏ đoạn cáp này khỏi hệ thống thì không thể truyền tin được từ máy u tới máy ~v~.

Yêu cầu

Hãy thêm một số ít nhất đoạn cáp sao cho hệ thống không còn bất kì đoạn cáp nào là xung yếu.

Dữ liệu

• Dòng đầu chứa 2 số nguyên dương ~n, m (n \leq 10^5, m \leq 2 \cdot 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên dương ~u_i, v_i~ xác định đoạn cáp thứ ~i~ của hệ thống (~1 \leq u_i, v_i \leq n~).

Kết quả

• Dòng duy nhất chứa số nguyên $k$ là số đoạn cáp tối thiểu cần thêm vào

Ví dụ

Input

4 4 
1 2 
1 3 
1 4 
2 3 

Output

1 

Giải thích

• Khi thêm cạnh ~(4, 2)~ vào thì hệ thống sẽ không còn đoạn cáp nào là xung yếu. Ngoài ra, còn một cách khác là thêm cạnh ~(4, 3)~.

Ở vùng quê của Thanh Huy có ~N~ làng và ~M~ con đường nối các làng này. Huy sẽ chọn tập hợp một số ngôi làng để tập thể dục sao cho nếu bỏ bất kỳ ngôi làng nào trong tập hợp đó ra thì Huy vẫn có thể đi qua các ngôi làng còn lại được bằng những đường nối các làng trong số đó.

Thanh Huy muốn xây thêm ~1~ con đường để có thể mở rộng con đường đi tập thể dục của mình nhưng Huy vẫn không biết nên xây lên con đường nào là tốt nhất, bạn hãy giúp anh ấy nhé.

Yêu cầu

Bạn hãy giúp Huy chọn ra ~1~ cặp làng mà sau có khi có con đường giữa hai làng đó, số làng có thể chọn để tập thể dục là nhiều nhất.

Dữ liệu

Đầu vào

• Dòng đầu chứa hai số nguyên dương ~N~ và ~M~ là số làng và số con đường nối các làng. (~1 \le N, M \le 5\cdot 10^5~)
• ~M~ dòng tiếp, mỗi dòng chứa hai số nguyên dương ~u~ và ~v~ là con đường nối làng thứ ~u~ và làng thứ ~v~ (~1 \leq u, v \leq n~, ~u \neq v~).
• Dữ liệu đảm bảo luôn tồn tại đường đi giữa 2 ngôi làng bất kỳ và giữa 2 ngôi làng chỉ có tối đa một con đường nối chúng trực tiếp.

Kết quả

• Gồm một dòng duy nhất chứa hai chỉ số của làng để tạo thêm đường.
• Nếu có nhiều phương án tối ưu thì in ra phương án bất kỳ.

Ví dụ

Input

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

Output

4 6 

Giải thích

• Xây dựng đường giữa làng thứ ~4~ và làng thứ ~6~ thì có thể chọn những làng là ~{1,2,3,4,6}~. Chọn làng ~4~ và ~5~ hay ~5~ và ~6~ để nối cũng là đáp án đúng.

Đất nước X gồm ~n~ thành phố, được kết nối với nhau bởi ~m~ con đường 2 chiều, biết rằng luôn tồn tại đường đi giữa 2 thành phố bất kỳ. Hiện đang có chuyến thăm của các lãnh đạo từ các nước láng giềng, biết rằng có ~k~ lãnh đạo và vị lãnh đạo thứ ~i~ hiện đang ở thành phố ~p_i~. Một con đường được gọi là quan trọng nếu như tồn tại một cặp ~(i, j)~ sao cho để đi từ thành phố ~p_i~ đến ~p_j~ bắt buộc phải sử dụng con đường này. ~(i, j \le k)~.

Do những con đường quan trọng tốn rất nhiều chi phí để bảo vệ và sửa sang, nên chính quyền quyết định mở thêm 1 con đường để giảm thiểu số con đường quan trọng.

Yêu cầu

Hãy giúp chính quyền của đất nước X đưa ra số con đường quan trọng tối thiểu có thể.

Dữ liệu

Đầu vào

• Dòng đầu gồm ba số nguyên dương ~n, m, k~ lần lượt là số thành phố, số con đường, số lãnh đạo tại đất nước X. (~1 \le k \le n \le 10^5~, ~1 \le m \le 3\cdot 10^5~)
• ~m~ dòng tiếp theo chứa 2 số nguyên dương ~u~, ~v~ thể hiện có đường 2 chiều giữa thành phố ~u~ và ~v~. (~u \neq v~, ~1 \leq u, v \leq n~)
• Dòng cuối cùng chứa ~k~ giá trị ~p_1, p_2, ... p_k~ thể hiện lãnh đạo thứ ~i~ đang ở thành phố ~p_i~.

Kết quả

• Xuất ra số lượng con đường quan trọng tối thiểu có thể tìm được.

Ví dụ

Input

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

Output

0

Giải thích

• Trong test ví dụ đầu tiên, nếu ta mở thêm con đường nối hai đỉnh ~2~ và ~5~ thì số con đường quan trọng ít nhất là ~0~
• Trong test ví dụ thứ 2 (hình bên dưới), với mọi cách mở thêm con đường tối ưu (các con đường ~(1, 8)~, ~(8, 6)~ và ~(1, 6)~) thì số con đường quan trọng ít nhất là ~1~

Trong lớp 10X có ~n~ bạn nam và ~n~ bạn nữ, mỗi bạn nam và nữ được đánh số từ ~1~ tới ~n~. Mối quan hệ quen biết của các bạn nam và nữ được biểu diễn bằng ~m~ cặp số ~a_i~, ~b_i~, thể hiện rằng bạn nam thứ ~a_i~ sẽ quen biết bạn nữ thứ ~b_i~. Bạn nam thứ ~i~ chắc chắn sẽ có mỗi quan hệ quen biết với bạn nữ thứ ~i~. Một bạn nam có thể quen biết nhiều bạn nữ và một bạn nữ cũng có thể quen biết nhiều bạn nam.

Sắp tới, trường dự định tổ chức một cuộc thi hát cho các bạn nữ tham gia và mời các bạn nam làm ban giám khảo. Để cuộc thi được thành công và công bằng thì nó phải thỏa các yêu cầu sau:

• Phải có ít nhất ~1~ giám khảo và ~1~ thí sinh.
• Tổng số giám khảo và thí sinh tham gia là ~n~.
• Các giám khảo không được quen biết thí sinh.

Yêu cầu

Tìm cách lựa chọn giám khảo và thí sinh thỏa yêu cầu trên

Dữ liệu

Đầu vào

Dòng đầu tiên gồm số nguyên dương ~t~, số bộ test (~1 \leq t \leq 10^5~). Với mỗi bộ test, cú pháp của chúng như sau:

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n~, ~m~ (~1 \leq n \leq m \leq 10^6~) là số học sinh nam hoặc nữ trong lớp và số mối quan hệ quen biết giữa các bạn.
• Trong ~m~ dòng tiếp theo, mỗi dòng gồm các số nguyên dương ~a_i~ và ~b_i~, thể hiện mối quan hệ hai chiều giữa bạn nam thứ ~a_i~ và bạn nữ thứ ~b_i~ (~1 \leq a_i, b_i \leq n~). Dữ liệu đảm bảo rằng mỗi cặp nam nữ chỉ xuất hiện nhiều nhất ~1~ lần và luôn tồn tại đúng ~n~ cặp có dạng (~i, i~) với mọi ~i~ từ ~1 \rightarrow N~.
• Dữ liệu đảm bảo rằng bạn nam thứ ~i~ luôn có mối quan hệ quen biết với bạn nữ thứ ~i~ và tổng ~n~, ~m~ của các bộ test không vượt quá ~10^6~.

Kết quả

Với mỗi bộ test:

• Dòng đầu tiên in ra "Yes" nếu tìm được cách chọn hợp lệ, "No" nếu không có cách chọn thỏa đề bài
• Dòng thứ ~2~ in ra ~j~ và ~p~ (~1 \leq j, p \leq n~, ~j + p = n~), số giám khảo và số thí sinh tham gia cuộc thi.
• Dòng thứ ~3~ in ra ~j~ số nguyên dương phân biệt từ ~1~ tới ~n~, chỉ số của các bạn nam được chọn làm giám khảo.
• Dòng thứ ~4~ in ra ~p~ số nguyên dương phân biệt từ ~1~ tới ~n~, chỉ số của các bạn nữ được chọn làm thí sinh.
• Nếu có nhiều cách chọn thì chỉ ra một cách thỏa bất kỳ.

Ví dụ

Input

4 
3 4  
1 1 
2 2  
3 3 
1 3 

3 7 
1 1  
1 2 
1 3 
2 2  
3 1 
3 2 
3 3 

1 1 
1 1 

2 4 
1 1 
1 2 
2 1 
2 2 

Output

Yes  
2 1  
1 3  
2  
Yes  
1 2 
2  
1 3 
No  
No  

Bạn có một đồ thị vô hướng liên thông gồm ~n~ đỉnh và ~m~ cạnh, các đỉnh được đánh số từ ~1~ tới ~n~. Bạn cần phải làm một trong hai công việc sau, tùy bạn lựa chọn:

1. Tìm một tổ hợp độc lập có lực lượng chính xác ~\lceil\sqrt{n}\rceil~ phần tử (ký hiệu ~\lceil x \rceil~ với ~x > 0~ là số nguyên bé nhất ~\geq x~; ví dụ: ~\lceil 4.2 \rceil = 5~, ~\lceil 4.7 \rceil = 5~, ~\lceil 4 \rceil = 4~).
   • Một tổ hợp độc lập là một tập hợp các đỉnh của đồ thị sao cho hai đỉnh bất kỳ trong tập hợp đều không có cạnh nối giữa chúng.
2. Tìm một chu trình đơn có độ dài không ít hơn ~\lceil\sqrt{n}\rceil~ đỉnh.
   • Một chu trình đơn là một chu trình chứa mỗi đỉnh không quá một lần.

Có thể chứng minh luôn có một trong hai công việc có thể làm được, nhưng bạn có thể thử chứng minh lại, tuỳ bạn.

Yêu cầu

Bạn hãy lựa chọn một trong hai công việc trên và in ra các đỉnh thỏa tính chất đó

Dữ liệu

• Dòng đầu chứa hai số nguyên dương là ~n,m~ - số đỉnh và số cạnh của đồ thị(~5 \le n \le 2\cdot10^5~, ~n-1 \le m \le min({n(n-1)\over2},5\cdot10^5)~).
• ~m~ dòng tiếp theo chứa hai số ~u,v~ thể hiện đồ thị có cạnh giữa ~u~ và ~v~ (~1 \leq u, v \leq n~).
• Dữ liệu vào đảm bảo đồ thị liên thông, giữa hai đỉnh bất kì chỉ có tối đa một cạnh và không có cạnh nào nối một đỉnh đến chính đỉnh đó.

Kết quả

Với mỗi bộ test:

• Nếu bạn chọn công việc 1: Dòng đầu in "1". Dòng tiếp theo in ~\lceil\sqrt{n}\rceil~ số nguyên dương là các đỉnh thuộc tổ hợp độc lập được chọn.
• Nếu bạn chọn công việc 2: Dòng đầu in "2". Dòng tiếp theo in một số nguyên dương ~k~ là độ dài của chu trình đơn tìm được. Dòng cuối in ~k~ số nguyên dương là các đỉnh thuộc chu trình đó, theo thứ tự xuất hiện trong chu trình.
• Nếu có nhiều đáp án, bạn hãy xuất ra đáp án bất kỳ, tùy bạn lựa chọn.

Ví dụ

Input 1

7 10 
1 2 
1 3 
1 4 
1 5 
1 6 
1 7 
3 4 
3 5 
3 7 
4 6 

Output 1

1 
2 4 7

Input 2

8 9
1 2
1 6
1 8
2 3
2 7
3 4
3 6
4 5
6 7

Output 2

2
4
1 6 3 2

Input 3

10 10
1 2
1 5
1 7
1 8
2 3
3 4
5 6
7 8
7 9
9 10 

Output 3

1
6 2 7 4

Note

• Chú ý ở test ví dụ đầu, một đáp án khác có thể là

2
4
4 1 7 3

Xét đoạn code sau:

dfs_order = [] # empty list
def DFS(u):
    visited[u] = True
    dfs_order.append(u)
        for vertex v that is directly connected to u:
        # note that the order of v is totally random
        if visited[v] == False:
            DFS(v)
DFS(random(1,n))

Trong đó:

• Mảng dfs_order sẽ lưu lại thứ tự DFS của đồ thị trên.

Cho một hoán vị của dãy số từ ~1~ tới ~n~, đếm xem có bao nhiêu cấu hình đồ thị khác nhau nhận hoán vị này là một thứ tự DFS hợp lệ. Hai cấu hình đồ thị ~G_1~ và ~G_2~ được gọi là khác nhau nếu tồn tại một cạnh trong ~G_1~ mà không có trong ~G_2~ hoặc ngược lại.

Yêu cầu

Bạn hãy in ra số cấu hình đồ thị thỏa thứ tự DFS được cho.

Dữ liệu

Đầu vào

• Dòng đầu gồm số nguyên dương ~n~ (~1 \leq n \leq 5000~).
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ biểu diễn một thứ tự DFS. Dữ liệu đảm bảo (~a_1, ..., a_n~) là một hoán vị của dãy số (~1, 2, ..., n~).

Kết quả

• Gồm một số duy nhất là số đồ thị nhận hoán vị trên là một thứ tự DFS hợp lệ theo modulo ~998\ 244\ 353~.

Ví dụ

Input 1

2
2 1

Output 1

1

Input 2

3 
3 1 2 

Output 2

3

Giải thích

• Trong test ví dụ đầu tiên, chỉ có một đồ thị, đồ thị đầy đủ kích thước nhận ~2, 1~ làm một thứ tự DFS hợp lệ.
• Trong test ví dụ thứ 2, có 3 đồ thị sau nhận ~3, 1, 2~ làm một thứ tự DFS hợp lệ: