짝 정하기

시간 제한1초메모리 제한128 MB

요약

세 초등학교 출신 남녀 학생들을 같은 학교 출신끼리는 짝지을 수 없게 완전 매칭이 가능한지 판별하고 가능하면 구체적인 매칭 방법을 구합니다.

문제

한 반에는 A, B, C 세 초등학교를 졸업한 남학생과 여학생이 있다. 남학생 수와 여학생 수는 각각 N명이다.

각 남학생은 여학생 한 명과 짝이 되어야 하며, 같은 초등학교 출신끼리는 짝이 될 수 없다. 모든 학생을 이 규칙에 맞게 정확히 한 번씩 짝지을 수 있는지 판단하고, 가능하다면 한 가지 짝 배정 방법을 출력하는 프로그램을 작성하시오.

첫째 줄에 남학생 수이자 여학생 수인 정수 N(3 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 넷째 줄까지는 A, B, C 초등학교 출신 학생 수가 순서대로 주어진다. 각 줄에는 해당 초등학교 출신 남학생 수와 여학생 수가 공백으로 구분되어 주어진다. 모든 학생 수는 0 이상이며, 남학생 수의 합과 여학생 수의 합은 각각 N이다.

모든 학생을 조건에 맞게 짝지을 수 없으면 첫째 줄에 0을 출력한다.

가능하면 첫째 줄에 1을 출력한다. 이어서 다음 세 줄에 아래 여섯 값을 공백으로 구분하여 출력한다.

가능한 방법이 여러 가지라면 아무 방법이나 출력한다.