СВЪРЖИ ТОЧКИТЕ

“Свържи точките” е игра за един играч. За да я играете, избирате две цели числа g и r, по-големи от 2. Начертавате 4 точки във върховете на квадрат, като горните две точки отбелязвате като зелени, а долните две като червени. Поставете зелени и червени точки вътре в квадрата така, че общият брой на зелените точки да бъде g, а на червените r и никои три точки (в това число и върховете на квадрата) да не лежат на една права. 

След като точките са поставени, започваме да ги съединяваме. Всеки две точки могат да бъдат съединени с праволинейна отсечка, ако
•	Двете точки са от един и същ цвят и
•	Отсечката, свързваща точките не пресича никоя друга отсечка, начертана преди.

Казваме, че точките u и v са от една и съща компонента, ако е възможно да преминем от u до v, движейки се по начертаните вече отсечки.

Вие сте победител, ако съедините всичките зелени точки в една компонента чрез точно g –1 отсечки и всичките червени точки в друга компонента чрез точно r – 1 отсечки. Може да се докаже, че при всяко разположение на точките, отговарящо на изискванията, има начин да победите в играта.

Дадена е квадратна дъска със страна s и g зелени и r червени точки върху дъската. Точките имат целочислени координатите (xi, yi). Зелените точки са номерирани от 1 до g, като най-горната лява точка има номер 1 и координати (0,s), най-горната дясна – номер 2 и координати (s,s), а останалите вътрешни зелени точки имат номера от 3 до g. Червените точки са номерирани от 1 до r, като най-долната лява точка има номер 1 и координати (0,0), най-долната дясна – номер 2 2 и координати (s,0), а останалите вътрешни червени точки имат номера от 3 до r. 

Фигурата показва пример за игра, където всички зелени точки са съединени в една компонента и всички червени точки – в друга компонента. Виждате, че никои две отсечки не се пресичат. 

 

ЗАДАЧА
Напишете програма, която по зададени координати на g зелени и r червени точки, намира търсените g - 1 зелени и r - 1 червени отсечки. 

ОГРАНИЧЕНИЯ
3 ≤ g ≤ 50 000		Брой на зелените точки.
3 ≤ r  ≤ 50 000 		Брой на червените точки.
0 < s ≤ 200 000 000 	

ВХОД

Програмата трябва да прочете следните данни от файла points.in 

points.in	ОПИСАНИЕ	
6
0 1000
1000 1000
203 601 
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400	Ред 1: Съдържа цялото число g.
Следващите g реда: Всеки ред съдържа две цели числа, разделени с интервал. Те задават координатите xi и yi на зелените точки.
Ред g+2: Съдържа цялото число r.
Следващите r реда: Всеки ред съдържа две цели числа, разделени с интервал. Те задават координатите xi и yi на червените точки.

ИЗХОД

Програмата трябва да запише следните данни във файла points.out 

points.out	ОПИСАНИЕ	
1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r
	Изходът трябва да съдържа (g – 1) + (r – 1) реда, по един за всяка начертана отсечка.
Всеки ред трябва да съдържа три отделени с интервал стойности: две цели числа и знак, представящ цвета на отсечката. Двете числа представят номерата на точките, съединени с отсечка. Знакът трябва да е g, ако точките са зелени, и r, ако точките за червени.
Последователността, в която извеждате отсечките не е съществена, нито редът на точките, които са краища на всяка отсечка. 

ОЦЕНЯВАНЕ

За част от тестове, които осигуряват общо 35 точки, е изпълнено: 3 ≤ g ≤ 20, 3 ≤ r ≤ 20.