Dream SMP Country Partitioning

In this problem, you are given (n) regions numbered from (0) to (n-1), which need to be partitioned among 8 countries numbered from (0) to (7). Each region must belong to exactly one country, though a country may end up with no regions at all.\n\nThere are (m) constraints provided. The (i)-th constraint is represented by four integers (u_i, a_i, v_i, b_i), which impose the condition that in any valid partitioning, it must hold that either region (u_i) is not assigned to country (a_i) or region (v_i) is not assigned to country (b_i) (logical OR). Formally, the constraint is satisfied if: [ (region_{u_i} \neq a_i) \quad \text{or} \quad (region_{v_i} \neq b_i)] \nIt is guaranteed that at least one valid partition exists. Your task is to construct any valid partitioning and output the country assignment for each region.

inputFormat

The first line contains two integers (n) and (m) denoting the number of regions and the number of constraints respectively.\n\nThen (m) lines follow, each containing four integers (u_i), (a_i), (v_i), and (b_i), representing a constraint as described above.

outputFormat

Output a single line containing (n) integers. The (i)-th integer represents the country assigned to region (i) (an integer between 0 and 7).

sample

3 1
0 1 1 2

0 0 0