766 . 圖與圖書館

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-graph

Description

小風是圖書館的志工，負責處理線上預約借書等雜務。一天，有 $N$ 本不同的書被開放預約，他發現使用預約系統的 $M$ 位客人每個人都恰好預約了兩本書，由於借書系統的限制，小風需要幫這些客人進行排序，接著按照順序，每一位客人都可以成功預約到所有還沒有被其他人預約過的書，萬一一名客人所有想借的書都被借走，他就會很生氣並投訴圖書館。小風想盡量避免此事發生，所以他必須妥善安排這些客人的順位，讓來投訴圖書館的客人越少越好，你能幫助他達成目標嗎？

Input Format

輸入第一行包含兩個正整數 $N, M (2 \leq N \leq 10^ 5, 1 \leq M \leq 10^ 5)$，分別代表書及客人的數量。
接下來 $M$ 行，每一行均有兩個正整數 $x, y (1 \leq x, y \leq N, x \neq y)$，代表某一位客人預約的書本號碼。

Output Format

請輸出一個整數代表最少可能來投訴圖書館的客人數量。

Sample Input 1

5 5
5 1
4 1
3 1
4 5
5 3

Sample Output 1

2

Sample Input 2

5 4
1 4
5 4
3 5
1 2

Sample Output 2

0

Hints

Problem Source

Codeforces

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~28 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
Submit
Back to Top