Wire-compatible Protocol buffer

Time limit3sMemory limit256 MB

Summary

Parse a protobuf descriptor and answer queries asking whether two message types are wire-format compatible given field tags, types, and labels.

Level: Medium7 of 10
Topics: Implementation, Hash map, Graph, DFS
Solved: No attempts yet

Problem

Protocol buffers (or protobuf) are a flexible, efficient, automated mechanism for serializing structured data. Think XML, but smaller, faster and simpler. In this problem, we will discuss the wire-compatible problem on a simplified protocol buffer.

Input

The first line contains an integer $n$ indicates the number of lines of a protobuf descriptor.

The following $n$ lines are the content of the protobuf descriptor which contains a set of messages. Each line will not contain more than 120 characters.

Then follows a line with an integer $m$ ( $1 \le m \le 50000$ ), indicating there are $m$ wire-format compatibility queries.

Then follow $m$ lines, each of which is a wire-format compatibility query with two message names.

It is guaranteed that the descriptor is valid, in other words, no two messages have the same name, no two fields in a message have the same field name or tag number, and each message type in a field must be one of the existing message names.

There will be at most 1000 messages in the descriptor, and each message will have at most 16 fields.

All tokens of the input are separated by spaces.

Output

For each query, output one line containing "Wire-format compatible." (quotes for clarity) if the two messages in this query are wire-format compatible, or otherwise, "Wire-format incompatible." (quotes for clarity)

Hint

In the first example:

For Test1 and Test2, though the two messages have different field names, the serialized message just cares about their field numbers.
For Test1 and Test3, the same field name as the two messages have, their field numbers do not match.
For Test1 and Test4, obviously required is incompatible with optional.
For Test1 and Test5, not all valid UTF-8 strings are valid messages, and vice versa.

Examples3

Example 1

Input

18
message Test1 {
  optional string field = 1 ;
}
message Test2 {
  optional string field_string = 1 ;
}
message Test3 {
  optional string field = 2 ;
}
message Test4 {
  required string field = 1 ;
}
message StringMessage {
  optional string field = 1 ;
}
message Test5 {
  optional StringMessage field = 1 ;
}
4
Test1 Test2
Test1 Test3
Test1 Test4
Test1 Test5

Expected output

Wire-format compatible.
Wire-format incompatible.
Wire-format incompatible.
Wire-format incompatible.

Example 2

Input

5
message A { optional B nest = 1 ; }
message B { optional C nest = 1 ; }
message C { }
message D { optional E nest = 1 ; }
message E { }
2
B D
A D

Expected output

Wire-format compatible.
Wire-format incompatible.

Example 3

Input

3
message A { optional A nest = 1 ; }
message B { optional C nest = 1 ; }
message C { optional B nest = 1 ; }
3
A B
A C
B C

Expected output

Wire-format compatible.
Wire-format compatible.
Wire-format compatible.