## Secret Santa

View as PDF

Points: 1.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

On the occasion of Christmas, Kuroni and ~n~ friends play a version of the game Secret Santa with Kuroni as the organizer. The game will take place over ~d~ days (with ~d~ chosen by Kuroni); the progress of each day is as follows:

• First, Kuroni selects ~k~ different friends ~u_1, u_2, \dots, u_k~, and proposes a positive real value ~w~. Note that ~k~, ~w~, and ~u_1, u_2, \dots, u_k~ may have different values for each day.

• Then, each selected friend will buy a gift worth exactly ~w~.

• Finally, the friends give the gifts they bought in a circle: ~u_1~ gives their gift to ~u_2~, ~u_2~ gives their gift to ~u_3~, ..., ~u_k~ gives their gift to ~u_1~.

To bring his ~n~ friends closer together, Kuroni has prepared a list of ~m~ pairs ~(u, v)~, with the idea that when this game ends, friend ~u~ must send at least one gift to friend ~v~; in addition, for pairs ~(x, y)~ not in his list, friend ~x~ is not allowed to send a gift to friend ~y~ (because that would make friend ~y~ misunderstand the intention of friend ~x~).

Of course, Kuroni also does not want any inappropriate feelings to arise among his ~n~ friends, so he wants that when the game ends, for every friend ~u~, the total values of gifts ~u~ had received from friends who had gifted ~u~ are the same. In other words, if ~v~ and ~t~ are two friends who had gifted ~u~, then the total value of gifts that ~v~ gave to ~u~ must be equal to the total value of gifts that ~t~ gave to ~u~ (otherwise, ~u~ will favor the friend who gave more gifts).

Kuroni has been racking his brain but has not yet found a way to arrange the game to achieve his wish. Can you help him?

#### Input

The first line contains two positive integers ~n~ and ~m~ (~1 \le n, m \le 200~) — the number of Kuroni's friends and the number of pairs in Kuroni's list.

The ~i~-th of the next ~m~ lines contains two positive integers ~u_i~ and ~v_i~ (~1 \le u_i, v_i \le n~) — representing the ~i~-th pair in Kuroni's list.

The input is guaranteed that there are no pairs that appear multiple times in the list, nor any pair that connects a friend to themself.

#### Output

On the first line, print "YES" (without quotes) if there exists a way to arrange the game to achieve Kuroni's wish; otherwise, print "NO" (without quotes).

If the first line is "YES", you need to print the number ~d~ no more than ~500~ of days that everyone will play on the second line. It can be proved that under the limit of this problem, if there exists a valid arrangement, there also exists an arrangement to play the game in no more than ~500~ days.

Next, you need to print ~d~ lines, with the ~i~-th line representing the ~i~-th day of the game. On each line:

• First, print a positive real not exceeding ~10^{15}~ ~w~ as the value for the gifts proposed on this day. It can be proved that under the limit of this problem, if there exists a valid arrangement, there also exists an arrangement such that the value of the gift on each day does not exceed ~10^{15}~.

• Next, print an integer ~k~ as the number of friends selected to play on the ~i~-th day.

• Finally, print ~k~ distinct positive integers ~u_1, u_2, \dots, u_k~ representing the selected friends (~1 \le u_j \le n~ for all ~1 \le j \le k~).

The values above should be printed on the same line, separated by spaces.

Define ~f(u \to v)~ as the total value of gifts that friend ~u~ has sent to friend ~v~ throughout the game. The judge will recognize that the arrangement of the game is valid if for every friend ~u~ and every two friends ~v~ and ~t~ who gave gifts to ~u~, the relative error between the total value of gifts that ~v~ gave to ~u~ and the total value of gifts that ~t~ gave to ~u~ does not exceed ~10^{-6}~; in other words, if ~x = f(v \to u)~ and ~y = f(t \to u)~, then ~\frac{|x - y|}{\min(x, y)} \le 10^{-6}~

The test data is generated such that if there exists a valid game arrangement, then there also exists an arrangement where for any two pairs ~(u, v)~ and ~(x, y)~ in the list, the ratio between ~f(u \to v)~ and ~f(x \to y)~ does not exceed ~10^{10}~. However, your output does not have to satisfy this condition.

#### Scoring

Assume that Kuroni's list corresponds to a directed graph ~G~ with ~n~ vertices and ~m~ edges, where each pair ~(u, v)~ corresponds to a directed edge ~u \to v~ in ~G~. Then:

1 1000 Each edge ~u \to v~ in ~G~ belongs to at most ~1~ simple cycle of ~G~
2 1000 Each edge ~u \to v~ in ~G~ satisfies ~u \lt v~, except for the edge ~n \to 1~
Total 3500

#### Sample Input 1

5 7
1 2
2 3
3 1
2 4
3 5
4 5
5 2


#### Sample Output 1

YES
3
1.0 3 1 2 3
0.5 3 2 3 5
0.5 3 2 4 5


#### Sample Input 2

3 4
1 2
2 1
1 3
2 3


#### Sample Output 2

NO


#### Sample Input 3

6 6
1 2
2 3
3 1
4 5
5 6
6 4


#### Sample Output 3

YES
2
0.3 3 1 2 3
0.6 3 5 6 4


#### Notes

In the first example, the following figures illustrate the initial graph ~G~, the game arrangement, and the total gift value that the friends gave to each other; the three days of playing are represented by three different colors.

The initial graph ~G~, the game arrangement, and the total gift value that the friends gave to each other.

Similarly, we have three figures below for the third example.

The initial graph ~G~, the game arrangement, and the total gift value that the friends gave to each other.