|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||6||1||1||100.000%|
A XOR gate has two inputs and one output. Its operation can be described by the following table
input 1 input 2 output 0 0 0 0 1 1 1 0 1 1 1 0
A system of XOR gates is called a XOR net if it has n inputs and one output and meets the following conditions:
The net of 6 gates is shown in the figure. It has 5 inputs and 1 output and meets conditions 1–5 so it is a XOR net. Observe that the numbers given in the figure do not agree with the fifth condition but there exists an appropriate numbering.
Inputs of a net are numbered from 1 to n. An input state of a XOR net can be described by an input word of the length n. Each letter of such a word is a binary digit 0 or 1. We assume that i-th digit of the word is a state of the i-th input of the net. For every input state the net returns 0 or 1 on its output. Each input word is a binary code of a natural number so we can order input words with respect to their values. We will test XOR nets by sending words from a fixed range to its input and counting the number of digits 1 returned on the output of the net.
Write a program that:
We assume that: 3 ≤ n ≤ 100, 3 ≤ m ≤ 3,000 and that the gates of the given net are numbered from 1 to m in an arbitrary order.
In the first line of the standard input there are three integers separated by single spaces. They are respectively: the number of inputs n of the given net, the number of gates m and the number of the gate connected to the output of the net.
In the following m lines there are descriptions of the connections between gates of the net. In the i-th line, for 1 ≤ i ≤ m, there is a description of the connections of two inputs of the i-th gate. Such a description consists of two integers from the range [-n,m] separated by a single space. If an input of the gate is connected to the k-th input of the net then the description of this connection is the negative integer -k, if this input is connected to the output of the j-th gate then it is described by the positive number j.
In the following two lines there are two n-bit words a and b. They represent lower and upper limits of the range in which we test the net. We assume that in the given range there is at most 100,000 words.
In the standard output there should be written a single non-negative integer — the number of words from the range a ≤ s ≤ b (where < is the relation consistent with the values of binary words), for which the XOR net returns 1 on its output.
5 6 5 -1 -2 1 3 1 -2 2 -3 4 6 -4 -5 00111 01110