Cho đồ thị vô hướng không có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Hãy đếm số thành phần liên thông của đồ thị đã cho.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả cạnh ~(u,v)~.

Output

• In ra số thành phần liên thông của đồ thị.

Điều kiện

• ~ 1 \le n,m \le 10^5~.

Ví dụ

Input 1:

4 3
1 2
2 3
3 4

Output 1:

1

Input 2:

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

Output 2:

2

Đất nước ~ABC~ gồm ~n~ thành phố, có ~m~ con đường hai chiều với độ dài là ~1~ nối giữa một cặp thành phố. Có ~k~ khách du lịch, vị khách thứ ~i~ đang ở thành phố ~a_i~. Hiện đang có một sự kiện xảy ra ở thành phố ~b~, với mỗi khách du lịch, hãy in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện này.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m,k~.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u~ và ~v~ miêu tả con đường ~(u,v)~.
• Dòng tiếp theo gồm ~k~ số nguyên dương miêu tả thành phố mà vị khách thứ ~i~ đang ở.
• Dòng cuối cùng chứa số nguyên dương ~b~ - thành phố nơi diễn ra sự kiện.

Output

• Với mỗi vị khách, in ra con đường ngắn nhất mà người đó phải đi để tới sự kiện.

Điều kiện

• ~ 1 \le n,m,k \le 2*10^5~.

Subtask

• ~50\%~ số điểm: ~n,m,k \le 1000~.
• ~50\%~ số điểm: Không giới hạn gì thêm.

Ví dụ

Input 1:

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

Output 1:

3 2 1

Input 2:

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

Output 2:

1 1 -1

Vùng đất Midland đang có chiến tranh tàn khốc. Bạn đang ở vùng giao tranh, và giờ phải gửi tài liệu mật từ đơn vì tới cho sở chỉ huy. Vùng này được biểu diễn dưới dạng một ma trận ~n \times m~, ô ở hàng ~i~ cột ~j~ được gọi là ô ~(i,j)~.

Đây là tài liệu mật và khẩn cấp, vậy nên bạn được lệnh phải tìm một đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Biết rằng bạn có thể đi sang ~4~ ô kề cạnh với ô đang đứng và mỗi ô ~(i,j)~ sẽ được miêu tả bằng một kí tự như sau:

• ~c(i,j) = .~, nếu đây là một ô bình thường có thể đi.
• ~c(i,j) = *~, đây là vùng nguy hiểm tuyệt đối không được đi vào.
• ~c(i,j) = S~, đây là đơn vị của bạn, sẽ chỉ có duy nhất một ô thế này xuất hiện.
• ~c(i,j) = T~, đây là sở chỉ huy, sẽ chỉ có duy nhất một ô thế này xuất hiện.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả kích thước bảng.
• ~n~ dòng sau, mỗi dòng gồm ~m~ kí tự miêu tả vùng đất.

Output

• In ra một dòng là đường đi ngắn nhất từ đơn vị tới sở chỉ huy. Nếu không có một đường đi nào như vậy, in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 1000~

Ví dụ

Input 1:

3 4 
S...
....
...T

Output 1:

5

Input 2:

3 4 
S.*T
*.*.
*...

Output 2:

7

Năm ~1976~, "Định lý bản đồ bốn màu" đã được chứng minh với sự hỗ trợ của máy tính. Định lý này cho rằng mọi bản đồ có thể được tô màu chỉ bằng bốn màu, theo cách mà không có vùng nào được tô màu sử dụng cùng màu với vùng lân cận.

Tuy nhiên, ở đây bạn được yêu cầu giải một bài toán tương tự nhưng đơn giản hơn. Bạn cần kiểm tra xem một đồ thị được cho có thể được "tô màu" hay không. Một đồ thị có thể coi là được "tô màu", nếu ta có thể gán một màu (chỉ sử dụng đúng hai màu) cho các nút sao cho không có hai nút liền kề nào có cùng màu.

Đồ thị được cho có một vài điều kiện như sau:

• Không có khuyên.
• Đồ thị vô hướng.
• Đồ thị liên thông.

Input

• Dòng thứ nhất gồm số nguyên dương ~t~ miêu tả số test case.
• Đối với mỗi test case:
  • Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả đỉnh của đồ thị. Lưu ý, các đỉnh trong đồ thị được đánh dấu từ ~0~ tới ~n-1~.
  • Dòng thứ hai gồm số nguyên dương ~m~ miêu tả số cạnh của đồ thị.
  • ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u,v~ miêu tả cạnh ~(u,v)~.

Output

• Với mỗi test case, in ra "BICOLORABLE." nếu có thể "tô màu" đồ thị, ngược lại in ra "NOT BICOLORABLE.".

Constraints

• ~1 \le t \le 20~
• ~1 \le n,m \le 200~

Sample Input 1:

3

3
3
0 1
1 2
2 0

3
2
0 1
1 2

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

Sample Output 1:

NOT BICOLORABLE.
BICOLORABLE.
BICOLORABLE.

Nitori Kawashiro cần thiết kế hệ thống cáp treo 2 chiều giữa ~n~ địa điểm. Biết rằng nếu có đường đi giữa địa điểm ~a~ tới địa điểm ~b~ và từ địa điểm ~b~ tới địa điểm ~c~ thì có thể đi từ ~a~ đến ~c~. Hãy cho biết cần xây dựng ít nhất bao nhiêu đường đi trực tiếp giữa 2 địa điểm để kết nối ~m~ cặp địa điểm cho trước.

Nói tóm lại, từ đồ thị được cho ban đầu, hãy tìm cách giữ lại ít cạnh nhất sao cho số vùng liên thông được giữ nguyên.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m \le 10^5~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 địa điểm ~u, v \le n~.

Output

• In ra một số ~p~ là số lượng đường đi trực tiếp giữa 2 địa điểm.
• ~p~ dòng sau mỗi dòng in ra 2 số ~u, v~ nghĩa là xây đường đi giữa 2 địa điểm ~u~ và ~v~.

Sample Test

Input:

4 2
1 2
1 4

Output:

2
1 2
2 4

Sau khi Kawashiro xây xong hệ thống cáp treo, cô lại phải tiếp tục xây dựng một số cáp treo nữa để tất cả địa điểm từ 1 đến ~n~ đều có thể đến đền Moriya nằm ở vị trí ~T~.

Input

• Dòng đầu gồm 3 số tự nhiên ~n, m, T \le 100000~.
• ~m~ dòng tiếp theo gồm 2 số ~u, v~ nghĩa là địa điểm ~u, v~ dã được nối bằng cáp treo một chiều.

Output

• Số lượng tối thiểu cáp treo cô cần xây thêm để mọi địa điểm từ 1 đến ~n~ đều đến được đền Moriya ở ~T~.

Sample Test

Input:

6 4 5
1 3
2 3
4 5
6 5

Output:

1

Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

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

Output 1:

2

Input 2:

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

Output 2:

-1