공통 친구
골드 IV의견: 0
소셜 네트워크에 \(N\)명의 사용자가 있고 \(M\)개의 친구 관계가 있다. 친구 관계는 양방향이고, 자기 자신과의 친구 관계는 없다.
\(Q\)개의 질문이 주어진다. 각 질문은 두 사용자 \(u\), \(v\)로 이루어지며, \(u\)와 \(v\) 모두와 친구인 사용자의 수를 물어본다. (\(u\) 자신이나 \(v\) 자신은 세지 않는다.) 각 질문에 답하여라.
- \(2 \le N \le 1\,000\)
- \(0 \le M \le N(N-1)/2\) (중복 없음, 자기 자신 없음)
- \(1 \le Q \le 5\,000\)
- 질문에서 \(u \ne v\)
첫째 줄에 사용자 수 \(N\), 친구 관계 수 \(M\), 질문 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 친구 관계를 나타내는 두 정수 \(u\), \(v\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 질문을 나타내는 두 정수 \(u\), \(v\)가 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 질문의 답을 순서대로 출력한다.
5 4 3
1 2
1 3
2 3
3 4
1 2
1 4
2 4
1
1
1
친구 \(1\)과 \(2\)의 공통 친구는 \(3\)뿐이어서 \(1\)이다. \(1\)과 \(4\)의 공통 친구는 \(3\)뿐이어서 \(1\)이다. \(2\)와 \(4\)의 공통 친구도 \(3\)이어서 \(1\)이다.
4 5 2
1 2
2 3
3 4
4 1
1 3
1 3
2 4
2
2
\(1\)과 \(3\)의 공통 친구는 \(2\)와 \(4\)로 \(2\)명이다. \(2\)와 \(4\)의 공통 친구는 \(1\)과 \(3\)으로 \(2\)명이다.
riseoj 작성
출처 Original
평가 및 의견
공통 친구
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
공통 친구