Problemas
최신식 P2P 프로그램이 정올학원에 유포되고 있다.
이 P2P로는 각종 문제들의 소스코드나 게임 등 학생들이 학업을 이어나가는데
방해되는 많은 파일들이 공유되고 있어서 정올학원의 서선생님이 이를 막고자 한다.
먼저 두 클라이언트가 직접적으로 연결되어 있을 수 있을 것이다.
이 P2P는 평등한 공유를 지향하기 때문에 두 노드의 직접 연결은 방향성을 따지지 않는다.
직접 연결되지 않은 두 노드는 직접 연결된 다른 노드들을 통해서 데이터를 주고받을 수 있다.
이 P2P의 단점이라면 임의의 두 노드 사이에 항상 간접 연결이 가능하다는 보장이 없다는 것이다.
서선생님은 어떤 하나의 연결을 끊어버림으로써 P2P 시스템을 패닉에 빠트리고자 한다.
그런데 아무 연결이나 끊는다고 해서 상황이 달라지는 것은 아니었다.
분명히 직접적인 연결은 끊었지만 다른 경로를 통해서 데이터가 전송될 수 있기 때문이다.
따라서 서로 데이터를 전송할 수 있던 어떤 두 클라이언트 사이의 경로가 없어져야만 시스템이 혼란에 빠질 것이다.
공격이 들키면 곤란하기 때문에 단 한 번의 공격으로 최대한 많은 혼란을 발생시키고자 한다.
구체적으로, N개의 클라이언트가 존재할 때 각각의 클라이언트를 ci(1≤i≤N)라 표현하면
혼란 순서쌍 집합 D = {(i, j) | 공격 이전에 ci와 cj 사이의 경로가 존재했으나 공격 이후에는 존재하지 않음}이 될 것이다.
서선생님은 혼란, 즉 |D|를 최대화하고자 한다. 어떤 두 클라이언트 사이의 직접 연결은 항상 하나 이하이다.
Entrada
입력의 첫 행은 클라이언트의 수 N(1≤N≤100,000)과 직접 연결의 수 C(0≤C≤100,000) 가 주어진다.
다음 C 개의 행에 걸쳐 직접 연결을 나타내는 두 정수 pi qi가 주어지며
이는 클라이언트 c(pi)와 c(qi) 사이의 직접 연결이 존재함을 의미한다.
Salida
입력에 대해 순서대로 최대 혼란 순서쌍 집합의 크기를 출력한다.
Ejemplo
6 5
3 1
4 1
5 2
6 2
1 2
9
Debes iniciar sesión para escribir código.