Fişierul intrare/ieşire:arborigami.in, arborigami.outSursăONI 2022 Baraj Seniori Ziua 2
AutorVlad GavrilaAdăugată deAlex_tz307Lorintz Alexandru Alex_tz307
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Miyuki vrea să împăturească arborigami

Kaguya, vicepreşedintele consiliului de studenţi, este răcită. Miyuki vrea, cum este tradiţional, să îi ofere cadou o mie de cocori de hârtie. Poate nu o mie... (prea exagerat pentru o simplă răceală), şi poate nu cocor... (prea tradiţional şi oricum nu am hârtie de origami...). Un arbore stea ar trebui să fie ideal!

Miyuki are un arbore (graf conex aciclic) format din N noduri numerotate de la 1 la N. El doreşte să îl transforme într-un arbore stea de dimensiune N − K, adică un graf conex aciclic care are cel puţin N − K − 1 frunze (noduri cu exact 1 vecin).

Pentru a transforma arborele său într-un arbore stea, Miyuki va efectua K operaţii de împăturire a câte două noduri. Pentru a i-a operaţie de împăturire, Miyuki:

  • Alege două noduri distincte ai şi bi existente în acel moment în arbore.
  • Notează cu V mulţimea vecinilor nodurilor ai şi bi (nodurile care au o muchie directă către cel puţin unul dintre ai sau bi).
  • Şterge din V nodurile ai şi bi, dacă acestea erau prezente.
  • Şterge din arbore nodurile ai şi bi, cât şi muchiile care aveau cel puţin un capăt într-unul din nodurile ai şi bi.
  • Adaugă în arbore un nod cu numărul N + i.
  • Adaugă muchii între nodul N + i şi fiecare din nodurile din mulţimea V.

După o astfel de operaţie, graful rezultat trebuie să fie în continuare arbore; mai precis, operaţia efectuată nu trebuie să introducă vreun ciclu. Altfel, operaţia este invalidă şi nu poate fi efectuată.

Deoarece nu vrea să pară că s-a străduit prea mult, Miyuki vrea să facă un număr K minim de operaţii. Pentru că secretara Chika a promis că nu îl mai învaţă nimic, trebuie să-l ajutaţi pe Miyuki să determine:

1. Care este numărul minim K de operaţii pentru a transforma arborele iniţial în arbore stea.

2. Care sunt cele K operaţii prin care arborele iniţial este transformat într-un arbore stea.

Date de intrare

De pe prima linie se va citi un singur număr natural N, reprezentând dimensiunea arborelui iniţial. Pe următoarele N − 1 linii vor fi descrise muchiile arborelui iniţial, pe linia i + 1 aflându-se două numere naturale ui şi vi, reprezentând nodurile unite de a i-a muchie din arbore.

Date de ieşire

Pe prima linie se va afişa un singur număr natural K, reprezentând numărul minim de operaţii ce trebuie efectuate. Pe următoarele K linii se vor afişa K perechi de numere naturale ai şi bi (1 ≤ i ≤ K), separate prin câte un spaţiu, reprezentând, în ordine, operaţiile de împăturire ce se efectuează asupra arborelui.

Restricţii

  • 1 ≤ N ≤ 500 000
  • Dacă există mai multe soluţii posibile, se poate afişa oricare.
  • Dacă se determină corect numărul minim de operaţii K, dar operaţiile afişate nu transformă corect arborele într-unul stea, sau una dintre operaţii este invalidă conform cu definiţia din enunţ, se va acorda 30% din punctaj.
#PunctajRestricţii
1
2
3
4
10
20
10
60
1 ≤ N ≤ 15
1 ≤ N ≤ 200
ui = i, vi = i + 1 pentru 1 ≤ i < N.
Nu există alte restricţii.

Exemplu

arborigami.inarborigami.outExplicaţii
5
1 2
2 3
3 4
4 5
1
2 4
Se efectuează o singură operaţie de împăturire, între nodurile 2 şi 4. Operaţia decurge în felul următor:
- vecinii nodurilor 2 şi 4 sunt V = 1, 3, 5
- ştergem nodurile 2 şi 4 din arbore
- adăugăm nodul N + 1 = 6 şi muchiile (1, 6), (3, 6), (5, 6)
Arborele final este cel compus din nodurile 1, 3, 5 şi 6 şi muchiile (1, 6), (3, 6), (5, 6).
Observăm că nodurile 1, 3 şi 5 au un singur vecin şi doar 6 are 3 vecini, deci arborele rezultat este stea.
6
1 2
2 3
3 4
4 5
5 6
2
2 4
5 7
Se efectuează două operaţii de împăturire:
- (2, 4), adăugând nodul N + 1 = 7;
- (5, 7), adăugând nodul N + 2 = 8.
Arborele final este cel compus din nodurile 1, 3, 6 şi 8 şi muchiile (1, 8), (3, 8), (6, 8).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?