21/11/2024 20:31:36

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1866. Eve

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Mitochondrial DNA is the Deoxyribonucleic acid molecule that is contained in mitochondria within cells of an organism.

Mitochondrial DNA is normally passed to a child exclusively from its mother. Because of this fact, it is possible to speak of "Mitochondrial Eve" which refers to the most recent common matrilineal ancestor of the entire population. Matrilineal ancestry is traced through female line: mother, grandmother, etc.

Mitochondrial Eve of the Earth's human population is estimated to have lived around `200\ 000` years ago, most likely in the East Africa.

In this problem, we consider a certain population of the same biological species (eukaryotic and anisogamous). The population has been observed for a period of time, and all births and deaths were clearly recorded. For some of the individuals within the population, their mitochondrial DNA was sequenced. It is assumed that each individual in the observed population received its mitochondrial DNA from its mother without any mutations.

Your task is to find out, whether all individuals currently alive have the same mitochondrial DNA.

The first line of the input file contains integer `n` (`1\ ≤\ n\ ≤\ 100\ 000`), the number of individuals that were alive at the beginning of the observation period. IDs of these individuals are integers from 1 to `n`.

Next `n` lines contain one character each. The `i`-th of these lines describes the sex of the individual with ID `i`. 'M' stands for male, 'F' stands for female.

The next line contains integer `m` (`0\ ≤\ m\ ≤\ 100\,000`), the total number of births and deaths that happened during the observation period.

Next `m` lines contain description of birth and death events, listed in chronological order.

A birth event is described by three space-separated tokens: the ID of the father, the ID of the mother, and a character that describes the sex of the child ('M' for male, 'F' for female). The ID given to the offspring is the smallest positive integer that hasn't been used as an ID by this point of time.

A death event is described by a single negative integer, whose absolute value equals the ID of the individual that died.

The next line contains integer `k` (`0\ ≤\ k\ ≤\ n\ +\ m`), the number of sequenced mitochondrial DNAs.

Each of the next `k` lines contains two space-separated integers, the ID of the individual whose mitochondrial DNA has been sequenced, and the unique identifier of the mitochondrial DNA of that individual. Unique identifiers of two mitochondrial DNAs are the same if and only if the corresponding sequenced mitochondrial DNAs are the same. All unique identifiers of the mitochondrial DNAs are integers from `1` to `10^9`.

All the data given in the input file is consistent and non-contradictory. Each individual's mitochondrial DNA was sequenced at most once. At least one individual was alive at the end of the observation period.

The output file must contain a single word:

YES –- if it can be derived that all the individuals that are alive at the end of the experiment have the same mitochondrial DNA;
NO –- if it can be derived that some of the individuals that are alive at the end of the experiment have different mitochondrial DNA;
POSSIBLY –- if none of the cases above takes place.

Sample Input #1

4
M
F
M
F
12
3 4 F
1 2 M
1 2 M
3 4 F
-3
-2
-4
-1
6 5 M
7 5 F
-7
-6
0

Sample Output #1

YES

Sample Input #2

Sample Output #2

YES

Sample Input #3

3
M
F
M
2
1 2 M
3 2 F
0

Sample Output #3

POSSIBLY

Sample Input #4

Sample Output #4

NO