Maximizing Semi-Empty Bins

You are given n balls numbered from 1 to n and m bins numbered from 1 to m. Each bin can hold at most 3 balls. However, each ball can only be placed into certain bins: there are e allowed conditions and the i-th condition is given by a pair \( (v_i, u_i) \), meaning that ball \( v_i \) may only be placed into bin \( u_i \).

Every ball must be placed into exactly one bin and the capacity of each bin must not be exceeded. A bin is called semi-empty if it contains at most one ball. Your task is to determine an assignment of balls to bins so that the number of semi-empty bins is maximized. In other words, if an assignment causes \( k \) bins to have two or more balls (recall that each bin can hold at most three balls), then the number of semi-empty bins is \( m - k \), which you must maximize.

The output should consist of two lines. The first line contains the maximum number of semi-empty bins attainable. The second line contains \( n \) integers, where the \( i\)-th integer is the assigned bin for ball \( i \) (if more than one optimal assignment exists, output any one of them).

Note: It is guaranteed that a feasible assignment exists.

inputFormat

The first line contains three integers: \( n \) (the number of balls), \( m \) (the number of bins), and \( e \) (the number of allowed conditions).

This is followed by \( e \) lines. Each line contains two integers \( v_i \) and \( u_i \), indicating that ball \( v_i \) can be placed in bin \( u_i \).

outputFormat

Output two lines:

• The first line is an integer representing the maximum number of semi-empty bins (i.e. the number of bins that contain at most one ball).
• The second line contains \( n \) integers. The \( i\)-th integer denotes the bin number in which ball \( i \) is placed.

sample

3 3 3
1 1
2 2
3 3

3
1 2 3