題目背景
土豪大學(xué)的計(jì)算機(jī)系開了一門數(shù)字邏輯電路課，第一個實(shí)驗(yàn)叫做“點(diǎn)亮數(shù)字人生”，要用最基礎(chǔ)的邏輯元件組裝出實(shí)際可用的電路。時間已經(jīng)是深夜了，盡管實(shí)驗(yàn)箱上密密麻麻的連線已經(jīng)拆裝了好幾遍，小君同學(xué)卻依舊沒能讓她的電路正常工作。你能幫助她模擬出電路的功能，成功點(diǎn)亮她的數(shù)字人生嗎？

問題描述
本題中，你需要實(shí)現(xiàn)一個簡單的數(shù)字邏輯電路模擬器。如果你已經(jīng)有了此方面的基礎(chǔ)，可以直接跳過本節(jié)。在閱讀時，也可以參照前兩個樣例的圖示和解釋，這有助于你更好地理解數(shù)字邏輯電路的工作原理。

數(shù)字邏輯電路是用來傳輸數(shù)字信號（也就是二進(jìn)制信號）的電路。一般來說，數(shù)字邏輯電路可以分為兩大類，即組合邏輯（combinational logic）電路和時序邏輯（sequential logic）電路。在本題中，我們僅關(guān)注組合邏輯電路。這種電路僅由邏輯門（logical gate）構(gòu)成。一個邏輯門可以理解為一個多輸入單輸出的函數(shù)，輸入端連接至少一個信號，而后經(jīng)過一定的邏輯運(yùn)算輸出一個信號。常見的邏輯門包括與（AND）、或（OR）、非（NOT）、異或（XOR）等，均與編程語言中的按位運(yùn)算是對應(yīng)的。

將一系列的邏輯門連接起來，就能構(gòu)成具有特定功能的電路。它的功能可能很簡單（如一位二進(jìn)制加法只需要一個異或門），也可能極其復(fù)雜（如除法）。無論復(fù)雜程度，這類電路的特點(diǎn)是：它不維持任何的狀態(tài)，任何時刻輸出只與輸入有關(guān)，隨輸入變化。真實(shí)世界中的邏輯器件由于物理規(guī)律的限制，存在信號傳播延時。為了簡單起見，本題中我們模擬的組合邏輯電路不考慮延時：一旦輸入變化，輸出立刻跟著變化。

考慮到組合邏輯電路的這一特性，設(shè)計(jì)時不能允許組合環(huán)路（combinational loop）的存在，即某邏輯門的輸入經(jīng)過了一系列器件之后又被連接到了自己的輸入端。真實(shí)世界中，這種做法將導(dǎo)致電路變得不穩(wěn)定，甚至損壞元器件。因此，你也需要探測可能的環(huán)路。需要注意，環(huán)路的存在性與邏輯門的具體功能沒有任何關(guān)系；只要連接關(guān)系上存在環(huán)路，電路就無法正常工作。

輸入格式
輸入數(shù)據(jù)包括若干個獨(dú)立的問題，第一行一個整數(shù)
，滿足
。接下來依次是這
個問題的輸入，你需要對每個問題進(jìn)行處理，并且按照順序輸出對應(yīng)的答案。

每一個問題的輸入在邏輯上可分為兩部分。第一部分定義了整個電路的結(jié)構(gòu)，第二部分定義了輸入和輸出的要求。實(shí)際上兩部分之間沒有分隔，順序讀入即可。

第一部分
第一行是兩個空格分隔的整數(shù)
，分別表示了整個電路的輸入和器件的數(shù)量，滿足
并且
。其中
和
都是與測試點(diǎn)編號有關(guān)的參數(shù)。

接下來
行，每行描述一個器件，編號從 1 開始遞增，格式如下：

FUNC k L_1 L_2 … L_k
None
其中 FUNC 代表具體的邏輯功能，
表示輸入的數(shù)量，后面跟著該器件的
個輸入端描述
，格式是以下二者之一：

Im：表示第 m 個輸入信號連接到此輸入端，保證
；
On：表示第 n 個器件的輸出連接到此輸入端，保證
。
所有可能的 FUNC 和允許的輸入端數(shù)量如下表所述：

FUNC 最少輸入數(shù)量 最多輸入數(shù)量 功能描述
NOT 1 1 非
AND 2
與
OR 2
或
XOR 2
異或
NAND 2
與非（先全部與后取非）
NOR 2
或非（先全部或后取非）
所有的器件均只有一個輸出，但這個輸出信號可以被用作多個器件的輸入。

第二部分
第一行是一個整數(shù)
，表示此電路需要運(yùn)行
次。每次運(yùn)行，都會給定一組輸入，并檢查部分器件的輸出是否正確。
滿足
，其中
是一個與測試點(diǎn)編號有關(guān)的參數(shù)。

接下來的
行為輸入描述，每一行的格式如下：

I_1 I_2 … I_M
None
每行有
個可能為 0 或 1 的數(shù)字，表示各個輸入信號（按編號排列）的狀態(tài)。

接下來的
行為輸出描述，每一行的格式如下：

s_i O_1 O_2 … O_s
None
第一個整數(shù)
表示需要輸出的信號數(shù)量。后面共有
個在
到
之間的數(shù)字，表示在對應(yīng)的輸入下，組合邏輯完成計(jì)算后，需要輸出結(jié)果的器件編號。

注意 O 序列不一定是遞增的，即要求輸出的器件可能以任意順序出現(xiàn)。

輸出格式
對于輸入中的
個問題，你需要按照輸入順序輸出每一個問題的答案：

如果你檢測到電路中存在組合環(huán)路，則請輸出一行，內(nèi)容是 LOOP，無需輸出其他任何內(nèi)容。

如果電路可以正常工作，則請輸出
行，每一行包含
個用空格分隔的數(shù)字（可能為 0 或 1），依次表示“輸出描述”中要求的各個器件的運(yùn)算結(jié)果。

樣例輸入1
1
3 5
XOR 2 I1 I2
XOR 2 O1 I3
AND 2 O1 I3
AND 2 I1 I2
OR 2 O3 O4
4
0 1 1
1 0 1
1 1 1
0 0 0
2 5 2
2 5 2
2 5 2
2 5 2
Data
樣例輸出1
1 0
1 0
1 1
0 0
Data
樣例1說明
本樣例只有一個問題，它定義的組合邏輯電路結(jié)構(gòu)如下圖所示。其功能是一位全加器，即將三個信號相加，得到一個兩位二進(jìn)制數(shù)。要求的器件 2 的輸出是向更高位的進(jìn)位信號，器件 5 的輸出是本位的求和信號。

p3.jpg

對于第一組輸入 0 1 1，輸出是 1 0；對于第二組輸入 1 0 1，輸出恰好依舊是 1 0（但電路內(nèi)部狀態(tài)不同）。

樣例輸入2
1
2 6
NOR 2 O4 I2
AND 2 O4 O6
XOR 2 O5 O1
NOT 1 O6
NAND 2 O2 O2
AND 2 I1 O3
2
0 0
1 0
3 2 3 4
6 1 2 3 4 5 6
Data
樣例輸出2
LOOP
Data
樣例2說明
本樣例也只有一個問題，它定義的組合邏輯電路結(jié)構(gòu)如下圖所示。

p4.jpg

這是一個帶組合環(huán)路的電路，因此無法正常工作。特別地，其中最短的環(huán)路有以下三條：

6 - 2 - 5 - 3 - 6
4 - 1 - 3 - 6 - 4
2 - 5 - 3 - 6 - 2
評測用例規(guī)模與約定

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.*;public class DigitalMock {static StreamTokenizer st=new StreamTokenizer(new BufferedInputStream(System.in));static int nextInt() throws IOException{st.nextToken();return (int)st.nval;}static String next() throws IOException{st.nextToken();return st.sval;}static int Q;//問題個數(shù)static int m;//信號輸入個數(shù)static int n;//器件個數(shù)static Nop nops[]=new Nop[550];static int head[]=new int[550];static int ne[]=new int[50000];static int to[]=new int[50000];static int cnt=1;static int du[]=new int[550];static void init(){//初始化Arrays.fill(head,0);Arrays.fill(nops,null);Arrays.fill(ne,0);Arrays.fill(to,0);Arrays.fill(du,0);cnt=1;}static void add(int u,int v){to[cnt]=v;ne[cnt]=head[u];head[u]=cnt++;}public static void main(String[] args) throws IOException{Q=nextInt();for (int i = 0; i < Q; i++) {init();m=nextInt();n=nextInt();for (int i1 = 1; i1 <=n; i1++) {String type=next();int inputsNum=nextInt();for (int j = 0; j < inputsNum; j++) {String in=next();char t=in.charAt(0);int u=Integer.valueOf(in.substring(1));du[i1]++;//起始輸入點(diǎn)if(t=='I'){add(u+n,i1);}//其他器件else{add(u,i1);}}Nop nop = new Nop(type);nops[i1]=nop;}for (int k = 1; k <=m; k++) {nops[k+n]=new Nop("SUPER");}int s=nextInt();List<List<Integer>> inputs = new ArrayList<>();List<List<Integer>> ques = new ArrayList<>();for (int i1 = 0; i1 < s; i1++) {List<Integer> sign = new ArrayList<>();for (int i2 = 0; i2 < m; i2++) {sign.add(nextInt());}inputs.add(sign);}for (int p = 0; p < s; p++) {int num=nextInt();List<Integer> q = new ArrayList<>();for (int i1 = 0; i1 < num; i1++) {q.add(nextInt());}ques.add(q);}if(isLoop()==false){System.out.println("LOOP");continue;}for (int i1 = 0; i1 < s; i1++) {query(inputs.get(i1),ques.get(i1));}}}static void query(List<Integer> input,List<Integer> ques){for (int i = 1; i <=n; i++) {//清空所有信號nops[i].input=new ArrayList<>();}for (int i = 1; i <= input.size(); i++) {nops[i+n].output=input.get(i-1);}topo();ArrayList<Integer> res = new ArrayList<>();for (Integer que : ques) {res.add(nops[que].getOut());}for (int i = 0; i < res.size(); i++) {System.out.printf(res.get(i)+" ");}System.out.println();}static boolean isLoop(){int visnum=0;int rudu[];rudu=du.clone();Queue<Integer> q=new LinkedList<>();for (int i = 1; i <=m+n; i++) {if(rudu[i]==0)q.offer(i);}while (!q.isEmpty()){Integer x = q.poll();//出隊(duì)visnum++;//訪問點(diǎn)+1for(int i=head[x];i!=0;i=ne[i]){int y=to[i];rudu[y]--;if(rudu[y]==0){q.offer(y);}}}return visnum==m+n;}static void topo(){int rudu[];rudu=du.clone();Queue<Integer> q=new LinkedList<>();for (int i = 1; i <=m+n; i++) {if(rudu[i]==0)q.offer(i);}while (!q.isEmpty()){Integer x = q.poll();//出隊(duì)for(int i=head[x];i!=0;i=ne[i]){int y=to[i];rudu[y]--;nops[y].input.add(nops[x].getOut());if(rudu[y]==0){q.offer(y);}}}}
}
class Nop{//NOT/AND/OR/XOR/NAND/NOR/SUPER(指輸入信號節(jié)點(diǎn)，超級節(jié)點(diǎn))String type;List<Integer> input;//輸入端int output=-1;//輸出端public Nop(String type) {this.type = type;this.input=new ArrayList<>();}public int getOut(){//計(jì)算輸出端結(jié)果if(output!=-1) return output;if(type.equals("NOT")){return input.get(0)==0?1:0;}else if(type.equals("SUPER")){return output;}else if(type.equals("AND")){for (Integer integer : input) {if(integer==0) return 0;}return 1;}else if(type.equals("OR")){for (Integer integer : input) {if(integer==1) return 1;}return 0;}else if(type.equals("XOR")){int res=0;for (Integer integer : input) {res^=integer;}return res;}else if(type.equals("NAND")){for (Integer integer : input) {if(integer==0) return 1;}return 0;}else{for (Integer integer : input) {if(integer==1) return 0;}return 1;}}
}