You are given a connected directed acyclicgraph with N vertices (2 <= N <= 20). Two players are playing the following game: First they put chip into some vertex of the graph. Then they in turns do the following: 1. Choose any edge, which goes from the vertex chip located in; 2. Move chip along this edge. Player, who cannot do his turn (because there are no outgoing edges from the current vertex) looses the game. For each vertex of the graph, determine will first player win the game or not, starting from this vertex, if both players are playing optimally. Input data specification On the first line of the input there are two integer numbers: N and M, where N is number of vertices and M is number of edges. Then M lines follow, each with two positive numbers A and B, describing edge going from vertex A to vertex B. Output data specification Produce N lines, each contains W if first player wins starting from the corresponding vertex, and L otherwise. Sample input 7 10 1 2 2 3 4 2 4 3 4 6 5 6 5 1 6 7 3 6 3 7 Sample output W L W W L W L Note Sample graph is the one which was described on the lecture. Find it on the 6th slide with the explanation how it works.