Cho ~G~ là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ ~1~. Có một đồng xu màu trắng đặt ở đỉnh ~w~ và một đồng xu màu đen đặt ở đỉnh ~b~. Hai người chơi một trò chơi trên ~G~ như sau:

• Hai người chơi luân phiên nhau thực hiện lượt chơi.
• Đến lượt mình, người chơi chọn một đồng xu bất kỳ và di chuyển nó. Nếu đồng xu màu trắng thì phải di chuyển theo các cung của đồ thị. Nếu đồng xu màu đen thì phải di chuyển ngược các cung của đồ thị. Tức là có thể di chuyển đồng xu màu trắng từ ~x~ sang ~y~ nếu ~(x, y)~ là một cung của đồ thị, và có thể di chuyển đồng xu màu đen từ ~u~ sang ~v~ nếu ~(v, u)~ là một cung của đồ thị.
• Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa.
• Nếu người chơi biết mình sẽ thắng, anh ta sẽ cố gắng thắng nhanh nhất có thể (cực tiểu hóa số lượt chơi).
• Nếu người chơi biết mình sẽ thua, anh ta sẽ cố gắng kéo dài thời gian (cực đại hóa số lượt chơi)

Biết rằng hai người chơi đều rất thông minh, hãy xác định số lượt chơi sẽ được thực hiện trong trò chơi.

Input

• Dòng đầu tiên chứa ~n~, ~m~, ~w~, ~b~ (~1 \leq n, m \leq 5000~, ~1 \leq w, b \leq n~) là số đỉnh, số cung, vị trí của đồng xu màu trắng, vị trí của đồng xu màu đen.
• ~m~ dòng tiếp theo mỗi dòng chứa một cung ~u~, ~v~ (~1 \leq u, v \leq n~).

Output

• Ghi một số nguyên là số lượt chơi sẽ được thực hiện.

Scoring

• Subtask 1 (~50\%~ số điểm): Đỉnh ~b~ không có cung đi vào.
• Subtask 2 (~50\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

 5

Có một trò chơi như sau:

• Có ~n~ viên bi
• Mỗi lượt chơi, người chơi lấy đi ba hoặc năm hoặc bảy hoặc chín viên bi (tất nhiên là nếu có đủ bi)
• Hai người luân phiên nhau thực hiện lượt chơi. Ai không thực hiện được lượt chơi nữa (tức số bi còn lại bé hơn ba) thì thua cuộc

Xác định ai là người chiến thắng, biết rằng cả hai đều chơi tối ưu.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ là số lượng testcase ~(1 \le T \le 10^5)~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~

Output

• Ghi ra ~T~ dòng, mỗi dòng ghi ~1/2~ tương ứng là người đi trước / sau thắng.

Sample Input

4
11
12
13
100

Sample Output

1
2
2
1

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi ít nhất một và nhiều nhất là tất cả số sỏi trong đống đó. Người không thể thực hiện được lượt đi hợp lệ (tức là khi tất cả các đống đều rỗng) sẽ thua cuộc.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số lượng đống sỏi ( ~1 \le N \le 10^5~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Sample Input 1

3
1 4 5

Sample Output 1

2

Sample Input 2

3
1 4 6

Sample Output 2

1

Có ~n~ đống sỏi, đống thứ i ban đầu có ~a_i~ viên sỏi.
Hai người chơi: bạn và Jury sẽ lần lượt thực hiện các lượt đi.

• Ở mỗi lượt, người chơi chọn một đống còn sỏi và lấy đi ít nhất 1 viên sỏi (và không nhiều hơn số sỏi hiện có trong đống đó).
• Người không thể thực hiện lượt đi hợp lệ (tức là tất cả các đống đều rỗng) sẽ thua.

Ban đầu bạn là người đi trước.
Jury sẽ chơi tối ưu, và bạn cần cố gắng chiến thắng trò chơi. Biết rằng input được sinh ra để bạn luôn có thể làm điều đó nếu chơi tối ưu.

Cách Thức Giao Tiếp

• Khi chương trình của bạn bắt đầu, Jury sẽ gửi cho bạn hai dòng đầu tiên:

  • Dòng 1: số nguyên ~n~ – số đống sỏi.
  • Dòng 2: chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ – số sỏi ban đầu trong mỗi đống.

• Sau đó, các lượt chơi diễn ra luân phiên như sau:

• Trò chơi kết thúc khi tất cả các đống đều rỗng.

Luật hợp lệ

• Mọi nước đi phải thoả mãn:
  • 1 ≤ x ≤ n
  • 1 ≤ y ≤ a[x] (trước khi lấy)
• Nếu bạn in ra giá trị không hợp lệ, chương trình sẽ bị dừng (TLE / Runtime Error).

Nhiệm vụ của bạn

Viết chương trình tương tác để chơi và chiến thắng trò chơi Nim với chiến lược tối ưu.

Giới hạn

• ~1 \leq n \leq 50~
• ~1 \leq a_i \leq 100~
• Số lượt tối đa: ~3 \times 10^5~

Ví dụ Minh Họa

Giả sử Jury có đầu vào:

3
1 2 3

Diễn tiến

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi ít nhất một và nhiều nhất là tất cả số sỏi trong đống đó. Người không thể thực hiện được lượt đi hợp lệ (tức là khi tất cả các đống đều rỗng) sẽ thua cuộc.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng.

Tuy nhiên, điểm đặc biệt ở phiên bản này, là bạn sẽ có một đống sỏi phụ ở bên ngoài. Đống sỏi này có ~M~ viên sỏi và sẽ không tính vào ~n~ đống sỏi của trò chơi. Ở mỗi lượt, bạn được thêm một lựa chọn, đó là lấy một lượng ~1 \le x \le M~ viên sỏi còn lại trong đống đó, rồi thêm các viên sỏi đó vào một đống sỏi tuỳ ý nào đó trong ~n~ đống sỏi.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, đồng thời tham số ~M~ là số viên sỏi của đống phụ, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, M~ - số lượng đống sỏi ( ~1 \le N \le 10^5; 1 \le M \le 10^9~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Sample Input 2

3 6
1 4 6

Sample Output 2

1

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi ~1 \le x~ viên sỏi thuộc đống đó. Tuy nhiên đây là phiên bản khó, nên mỗi đống sỏi bạn sẽ chỉ được lấy tối đa ~B_i~ viên mà thôi. Người không thể thực hiện được lượt đi hợp lệ (tức là khi tất cả các đống đều rỗng) sẽ thua cuộc.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số lượng đống sỏi ( ~1 \le N \le 10^5~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~B_1, B_2, \dots, B_N~ ( ~1 \le A_i \le 10^9~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Const:

• Có ~25\%~ số test có ~N = 1~.

Sample Input 1

1
28
6

Sample Output 1

2

Sample Input 2

2
8 18
3 5

Sample Output 2

2

Trò chơi Nim là một trò chơi hai người rất nổi tiếng trong lý thuyết trò chơi. Ban đầu có ~N~ đống sỏi, trong đó đống thứ ~i~ có ~A_i~ viên sỏi. Hai người chơi lần lượt thực hiện lượt đi, người chơi thứ nhất đi trước.

Ở mỗi lượt, người chơi được chọn một đống sỏi bất kỳ còn ít nhất 1 viên, rồi lấy đi một số viên sỏi ở đó thoả mãn:

• Gọi ~x~ là số viên sỏi ở đống sỏi mà người chơi chọn. Gọi ~y~ là số viên sỏi mà người chơi sẽ lấy ra, ~y~ phải là một số nguyên dương thoả mãn ~gcd(x,y) = 1~.

Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ là người chiến thắng, biết rằng nếu đến lượt ai mà người đó không thể thực hiện lượt chơi thì sẽ thua.

Yêu cầu: Cho biết số lượng đống sỏi và số sỏi trong từng đống, hãy in ra:

• ~1~ nếu người chơi thứ nhất (An) chắc chắn thắng,

• ~2~ nếu người chơi thứ hai (Bình) sẽ thắng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ - số lượng đống sỏi ( ~1 \le N \le 10^5~ ).

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^7~ ).

Output

• Ghi ra một số duy nhất - 1 hoặc 2, biểu thị người chiến thắng của trò chơi.

Sample Input 1

4
3 3 6 1

Sample Output 1

1

Sample Input 2

5
1 2 3 4 5

Sample Output 2

2

Cho ~G~ là một đồ thị có hướng không có chu trình, các đỉnh được đánh số từ 1 đến ~n~. Tại đỉnh thứ ~i~ có một số nguyên dương ~a_i~. An và Bình chơi một trò chơi như sau:

• Hai người chơi luân phiên nhau thực hiện lượt chơi, An đi trước
• Đến lượt mình, người chơi chọn một đỉnh ~i~ tùy ý, sau đó anh ta chia ~a_i~ cho một ước tùy ý (lớn hơn 1) của ~a_i~, sau đó với mỗi đỉnh ~j~ kề với ~i~ anh ta có thể tăng ~a_j~ lên một lượng là số nguyên không âm tùy ý (các đỉnh khác nhau có thể tăng một lượng khác nhau).
• Ai không thực hiện được lượt chơi hợp lệ nữa sẽ thua cuộc. Rõ ràng là trò chơi sẽ kết thúc sau hữu hạn bước, nên sẽ không có kết quả hòa. Biết rằng hai người chơi đều rất thông minh, hãy xác định ai là người chiến thắng

Input

Dòng đầu tiên chứa ~T~ là số lượng testcase, với mỗi testcase:

• Dòng đầu tiên chứa ~n~ ~m~: số đỉnh và số cung của đồ thị
• Dòng tiếp theo chứa ~a_1~ ~a_2~ ~\ldots~ ~a_n~
• ~m~ dòng tiếp theo mỗi dòng chứa một cung: ~u~ ~v~

Output

• Với mỗi testcase, ghi ra trên một dòng 1/0 tương ứng là An/Bình chiến thắng

Scoring

• Trong tất cả các test: Tổng ~n~ và tổng ~m~ trong ~T~ testcase đều không quá ~10^5~, ~1\leq a_i \leq 10^9~
• Subtask ~1~ (~10\%~ số điểm): ~m=0~ và ~a_i \leq 10^5~
• Subtask ~2~ (~20\%~ số điểm): ~m=0~
• Subtask ~3~ (~30\%~ số điểm): ~a_i \leq 10^5~
• Subtask ~4~ (~40\%~ số điểm): không ràng buộc gì thêm

Example

Sample Input 1

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

Sample Output 1

0
1 

Các bạn đọc đề ở link sau:

https://oj.vnoi.info/problem/voi22_matrix

Bài này chúng ta không quan trọng việc code mà sẽ đi chứng minh tại sao công thức đúng và cách tiếp cận các dạng bài tương tự.