English · Original
Chinese · Translation
Formal · Original
Soon the first year students will be initiated into students at the University of Berland. The organizers of the initiation come up with a program for this holiday. In their opinion, it would be good if the first-year students presented small souvenirs to each other. When they voiced this idea to the first-year students, they found out the following:
* some pairs of the new students already know each other;
* each new student agrees to give souvenirs only to those with whom they are already familiar;
* each new student does not want to present too many souvenirs.
The organizers have written down all the pairs of first-year friends who are familiar with each other and now want to determine for each new student, whom they should give souvenirs to. In their opinion, in each pair of familiar students _exactly one_ student must present a souvenir to another student.
First year students already decided to call the unluckiest the one who will have to present the greatest number of souvenirs. The organizers in return promised that the unluckiest will be unlucky to the minimum possible degree: of course, they will have to present the greatest number of souvenirs compared to the other students, but this number will be as small as possible.
Organizers are very busy, and they asked you to determine for each pair of first-year friends who and to whom should present a souvenir.
## Input
The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 5000, 0 ≤ _m_ ≤ _min_(5000, _n_·(_n_ - 1) / 2)) — the number of the first year students and the number of pairs of the students that know each other. The students are numbered from 1 to _n_.
Each of the following _m_ lines contains two integers _x__i_, _y__i_ (1 ≤ _x__i_, _y__i_ ≤ _n_, _x__i_ ≠ _y__i_) — the students in each pair.
It is guaranteed that each pair is present in the list exactly once. It is also guaranteed that if there is a pair (_x__i_, _y__i_) in the list, then there is no pair (_y__i_, _x__i_).
## Output
Print a single integer into the first line — the smallest number of souvenirs that the unluckiest student will have to present.
Following should be _m_ lines, each containing two integers — the students which are familiar with each other. The first number in the pair must be the student that will present the souvenir to the second student in the pair.
Pairs can be printed in any order. If there are many solutions, print any of them.
[samples]
不久，贝兰大学的一年级新生将举行入学仪式。组织者为这一节日设计了一个节目。他们认为，如果新生们互相赠送小礼物，将会很好。当他们向新生们提出这个想法时，得到了以下反馈：
组织者已经记录下了所有彼此熟悉的新生对，现在希望为每个新生确定该把礼物送给谁。在他们看来，对于每一对熟悉的学生，<em>恰好有一个人</em>需要向另一个人赠送礼物。
新生们已经决定，将赠送礼物数量最多的人称为“最不幸的人”。组织者承诺，他们会尽量减轻最不幸者的不幸程度：当然，他必须比其他所有学生送出更多的礼物，但这个最大值将尽可能小。
组织者非常忙碌，因此请你为每一对熟悉的一年级新生确定谁应该向谁赠送礼物。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 5000]，#cf_span[0 ≤ m ≤ min(5000, n·(n - 1) / 2)]）——分别表示一年级新生人数和彼此熟悉的学生对数。学生编号从 #cf_span[1] 到 #cf_span[n]。
接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[xi, yi]（#cf_span[1 ≤ xi, yi ≤ n]，#cf_span[xi ≠ yi]）——表示每一对熟悉的学生。
保证每对关系在列表中仅出现一次。同时保证，如果列表中存在对 #cf_span[(xi, yi)]，则不会存在对 #cf_span[(yi, xi)]。
请在第一行输出一个整数——最不幸的学生必须送出的最少礼物数量。
接下来输出 #cf_span[m] 行，每行包含两个整数，表示一对熟悉的学生。每对中第一个数字是赠送礼物的学生，第二个数字是接收礼物的学生。
可以按任意顺序输出这些对。如果有多种解，输出任意一种即可。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 5000]，#cf_span[0 ≤ m ≤ min(5000, n·(n - 1) / 2)]）——分别表示一年级新生人数和彼此熟悉的学生对数。学生编号从 #cf_span[1] 到 #cf_span[n]。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[xi, yi]（#cf_span[1 ≤ xi, yi ≤ n]，#cf_span[xi ≠ yi]）——表示每一对熟悉的学生。保证每对关系在列表中仅出现一次。同时保证，如果列表中存在对 #cf_span[(xi, yi)]，则不会存在对 #cf_span[(yi, xi)]。
## Output
请在第一行输出一个整数——最不幸的学生必须送出的最少礼物数量。接下来输出 #cf_span[m] 行，每行包含两个整数，表示一对熟悉的学生。每对中第一个数字是赠送礼物的学生，第二个数字是接收礼物的学生。可以按任意顺序输出这些对。如果有多种解，输出任意一种即可。
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of students, $ m \in \mathbb{Z} $ the number of undirected edges (friendships).
Let $ G = (V, E) $ be an undirected graph with $ V = \{1, 2, \dots, n\} $ and $ E = \{ \{x_i, y_i\} \mid i \in \{1, \dots, m\} \} $.
**Constraints**
1. $ 1 \leq n \leq 5000 $
2. $ 0 \leq m \leq \min\left(5000, \frac{n(n-1)}{2}\right) $
3. Each edge $ \{x_i, y_i\} \in E $ is unique and $ x_i \ne y_i $.
**Objective**
Assign a direction to each edge $ \{x_i, y_i\} \in E $, producing a directed graph $ D = (V, A) $, such that:
- For each undirected edge $ \{x, y\} \in E $, exactly one of $ (x, y) $ or $ (y, x) $ is in $ A $.
- Let $ d^+(v) $ denote the out-degree of vertex $ v $ in $ D $.
- Minimize $ \max_{v \in V} d^+(v) $.
**Output**
1. The value $ \min \max_{v \in V} d^+(v) $.
2. A list of $ m $ directed edges $ (u, v) \in A $, representing who gives a souvenir to whom.
API Response (JSON)
{
"problem": {
"name": "J. Students Initiation",
"description": {
"content": "Soon the first year students will be initiated into students at the University of Berland. The organizers of the initiation come up with a program for this holiday. In their opinion, it would be good ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF847J"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Soon the first year students will be initiated into students at the University of Berland. The organizers of the initiation come up with a program for this holiday. In their opinion, it would be good ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "不久，贝兰大学的一年级新生将举行入学仪式。组织者为这一节日设计了一个节目。他们认为，如果新生们互相赠送小礼物，将会很好。当他们向新生们提出这个想法时，得到了以下反馈：\n\n组织者已经记录下了所有彼此熟悉的新生对，现在希望为每个新生确定该把礼物送给谁。在他们看来，对于每一对熟悉的学生，<em>恰好有一个人</em>需要向另一个人赠送礼物。\n\n新生们已经决定，将赠送礼物数量最多的人称为“最不幸的人”。组...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of students, $ m \\in \\mathbb{Z} $ the number of undirected edges (friendships). \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{1, 2, ...",
"is_translate": false,
"language": "Formal"
}
]
}