An và Bình chơi một trò chơi tô màu trên đồ thị có \(N\) đỉnh và \(M\) cạnh. Có \(C\) màu được đánh số từ \(1\) đến \(C\). Mỗi lượt, người chơi chọn một đỉnh chưa được tô và tô nó bằng một màu bất kỳ (từ \(1\) đến \(C\)) sao cho không có hai đỉnh kề nhau nào có cùng màu. Người nào đến lượt mình mà không thể tô được đỉnh nào sẽ thua. Cả hai đều chơi tối ưu.

Hãy xác định người thắng cuộc.

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên \(N\), \(M\), \(C\) (\(1 \le N \le 20\), \(0 \le M \le \frac{N(N-1)}{2}\), \(1 \le C \le 4\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le N, u \neq v\)) biểu diễn một cạnh vô hướng.

Định dạng đầu ra

• In ra \(1\) nếu An (người đi trước) thắng, \(2\) nếu Bình thắng.

Ví dụ

Input:

3 2 2
1 2
2 3

Output:

1

Ràng buộc