TLEoj Contest #02 - Thành phố Đà Lạt

Điểm: 900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Mạng lưới giao thông của thành phố Đà Lạt bao gồm $n$ địa điểm và $m$ con đường một chiều, mỗi con đường nối hai địa điểm với nhau.

Để cải thiện khả năng thu hút khách của thành phố, chính quyền quyết định chia $m$ con đường thành hai nhóm, sao cho với mỗi nhóm đều thỏa mãn tính chất: nếu từ địa điểm $i$ có thể đi đến địa điểm $j$ bằng các con đường trong một nhóm, thì sẽ không thể quay lại địa điểm $i$ từ địa điểm $j$ bằng các con đường trong cùng nhóm đó. Điều này sẽ buộc các du khách đi thăm mỗi địa điểm không quá một lần.

Bạn hãy chỉ ra một cách chia $m$ con đường bất kỳ thỏa mãn điều kiện nêu trên.

Input, Output và Subtasks

Input

Dòng thứ nhất gồm 1 số $t$ là số testcase ( $1\le t\le 100$ )
Sau đó là $t$ block được định dạng như sau:
- Dòng đầu gồm 2 số $n$ và $m$ ( $1\le n\le 100,1 \le m \le n \times (n-1)$ )
- $m$ dòng tiếp theo, mỗi dòng gồm 2 số $u_i$ và $v_i$ ( $u_i\ne v_i$ ) cho biết có đường đi một chiều từ $u_i$ đến $v_i$ . Dữ liệu đảm bảo các đường đi không trùng nhau, nghĩa là không có 2 giá trị $i,j$ thỏa mãn $u_i=u_j,v_i=v_j$ (nhưng có thể có hai giá trị $i, j$ sao cho $u_i = v_j, v_i = u_j$ )
- Input mẫu có chứa một số dòng trống, để bạn dễ phân biệt các block với nhau (nhưng trong test chấm thì sẽ không có những dòng trống này)

Output

Xuất ra $t$ dòng tương ứng với kết quả từng testcase, mỗi dòng xuất ra $m$ giá trị $1$ hoặc $2$ , nếu giá trị thứ $i$ là $1$ tức là bạn chia con đường thứ $i$ vào phần $1$ , ngược lại bạn chia con đường thứ $i$ vào phần $2$ . Nếu có nhiều kết quả cùng thỏa mãn, chỉ cần in ra một kết quả bất kỳ.

Scoring

Subtask 1 ( $20\%$ ): $t=1;n,m\le 20$
Subtask 2 ( $80\%$ ): Không có ràng buộc gì thêm

Sample

Input

Output

221
111

Bình luận

Không có bình luận nào.