Maximizing Even-Friend Parties

The Byzantine king is hosting two grand parties and wants to invite as many residents as possible. Based on his extensive experience, he knows that a resident is very happy if, at the party they attend, they encounter an even number of their friends. Friendship is a symmetric relation (i.e. if A knows B then B knows A). Your task is to assign each resident to one of the two parties such that the number of residents with an even number of friends within the same party is maximized.

More formally, you are given an undirected graph with n vertices (residents) and m edges (friendships). You need to partition the vertices into two groups. For each vertex, count the number of neighbors in the same group. A vertex is happy if that number is even. Output an assignment (either 1 or 2 for each resident) that maximizes the number of happy vertices.

Note: If a resident has no friend at the party (i.e. 0, which is even), he/she is also considered happy.

Remark: This problem may be NP-hard in general. A heuristic or local search algorithm that gradually improves the assignment is acceptable.

inputFormat

The first line contains two integers n and m — the number of residents and the number of friendships.

The following m lines each contain two integers u and v (1-indexed) representing a friendship between residents u and v.

outputFormat

Output a single line with n integers. The i-th integer should be either 1 or 2 indicating the party that resident i attends. This assignment should maximize (or heuristically aim to maximize) the number of residents who have an even number of friends in the same party.

sample

3 2
1 2
2 3

1 2 1