Bataille par élimination – Regional event 2020

Énoncé¶

Les forces de l'empire se sont réparties sur une planète à la topologie un peu complexe. Les pentes de certaines montagnes sont tellement raides qu'on ne peut que les descendre ! L'empire a déployé l'ensemble de ses soldats en petites troupes partout sur la planète. Cependant la rébellion possède sur cette planète un puissant dispositif de souterrains (complètement indétectables par les troupes ennemies) qui lui permet de se déplacer très vite d'une montagne à une autre.

La rébellion prépare son plan d'attaque et anticipe ainsi la réaction des troupes ennemies : si une troupe est attaquée à un point donné, toutes les troupes en mesure de les rejoindre arrivent instantanément leur venir en aide.

Toutefois, les rebelles ne pourront gagner la bataille que s'ils sont strictement plus nombreux que les soldats de l'empire. En revanche, s'ils gagnent, ils restent tous vivants et peuvent tous aller attaquer autre part.

Ils souhaitent donc comprendre quels points il faut attaquer en premier et en déduire le nombre minimum de rebelles nécessaires pour neutraliser l'ensemble des troupes de l'empire.

Entrée¶

L'entrée contiendra :

• Sur la première ligne, un entier : $N$, le nombre de troupes de soldats de l'empire.
• Sur la ligne suivante, une liste de $N$ entiers séparés par des espaces : $S_i$, le nombre de soldats de la troupe.
• Sur la ligne suivante, un entier : $M$, le nombre de chemins (dirigés) possibles d'une troupe à une autre.
• Sur les lignes suivantes, une liste de $M$ éléments : $chemins$, la liste des chemins possibles.
  • Une ligne par élément de la liste : séparés par des espaces, un entier $a_j$ (la première troupe qui peut rejoindre la deuxième), et un entier $b_j$ (la troupe qui peut être rejointe).

Sortie¶

Affichez le nombre minimal de rebelles pour vaincre à toutes les batailles.

Contraintes¶

• $ 1 \leq N \leq 50000 $
• $ 1 \leq S_i \leq 100 $
• $ 1 \leq M \leq 70000 $
• $ 1 \leq a_j \leq N $
• $ 1 \leq b_j \leq N $