The famous billionaire Bajtelon has just bought a social network. He quickly realized that for this investment to pay off, he would need to make a series of changes to attract new advertisers. To start, he will try to create more buzz around his network by promoting extreme opinions on the current Hot Topic.

There are $n$ users registered on the service, connected by $m$ symmetric friendship relations. Each user can have one of $k$ opinions on the Hot Topic (for simplicity, opinions are numbered with integers from $1$ to $k$, where $k$ denotes total approval and $1$ denotes total disapproval).

Bajtelon can, through appropriately chosen advertisements, convince each user to an opinion of his choosing (opinions are chosen individually for each user). He wants to do this so that, in the end: each user sees different but similar opinions among their friends (specifically: the opinions of friends must differ by exactly $1$ from their own opinion); the number of people with extreme opinions ($1$ or $k$) is as large as possible.

Help him choose the opinions that he should assign to each user.

Input

The first line of input contains three integers $n$, $m$, and $k$ ($3 \le n \le 200$, $0 \le m \le n(n-1)/2$, $3 \le k \le n$), representing the number of users in the network, the number of friendship relations, and the number of opinions, respectively. Users are numbered from $1$ to $n$.

The next $m$ lines contain the friendship relations; each contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \neq b$), meaning that users $a$ and $b$ are friends on the service. No friendship will be listed more than once.

Output

If it is impossible to assign opinions according to Bajtelon's requirements, output exactly one line containing the word NIE.

Otherwise, output exactly two lines. The first line should contain a single integer $s$, representing the maximum number of users with opinions $1$ or $k$ in a valid assignment of opinions to all people.

The second line should contain a sequence of $n$ integers from the range $[1, k]$ separated by single spaces; the $i$-th of these numbers should represent the opinion of user $i$ in a valid assignment. This sequence must contain exactly $s$ people with opinion $1$ or $k$.

Examples

Input 1

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

Output 1

5
2 3 4 3 1 1 4 4

Note 1

Explanation of the figure: The dots in the figure represent network users, and the lines represent friendship relations. The number next to a dot indicates the user's ID, and the number in parentheses is their final opinion on the Hot Topic. There are 5 people with extreme opinions (1 or 4).

Input 2

3 3 3
1 2
2 3
3 1

Output 2

NIE

Subtasks

If it is possible to assign opinions according to Bajtelon's requirements (i.e., the answer is not NIE), and your program correctly outputs only the first line of the output, it will receive 50% of the points for that test. In particular, to receive these 50% of points for a test, you do not need to output the second line.