Circular Network
Time limit2sMemory limit128 MB
Given a cycle of N nodes and P path requests, choose a direction for each request to minimize the total number of distinct cycle edges converted.
- Level
Medium6 of 10
- Topics
- Greedy, Bit manipulation, Combinatorics
- Solved
- No attempts yet
Problem
N computers are connected in a circle. The computers are numbered from 1 to N, and each computer is connected by network lines to the computers on both sides. Computer 1 and computer N are also connected, so all lines together form one cycle.
Some of these lines will be converted to fiber-optic lines. You are given P requests, each asking for a fiber-optic path between computer p and computer q.
To satisfy one request, choose one of the two directions between p and q and convert every line on that path. For instance, if N=3 and computers 1 and 2 must be connected, you may convert only line 1-2, or you may convert lines 2-3 and 3-1.
Find the minimum number of lines that must be converted to satisfy all requests.
Input
The first line contains two integers N and P. (1 ≤ N ≤ 1,000, 1 ≤ P ≤ 10,000)
Each of the next P lines contains two computer numbers p and q describing one request.
Output
Print one integer X, the minimum number of lines needed to satisfy every request.