Game - MarisaOJ: Marisa Online Judge
The given problem describes a game with $n$ levels, each on a different map. For each level, a player selects a car from three types: `A`, `B`, and `C`. There are four types of maps denoted by the characters `x`, `a`, `b`, and `c`. Some restrictions apply, such as not using car `A` for map `a`, not using car `B` for map `b`, and not using car `C` for map `c`. However, all three types of cars can be used for map `x`.
The maps for each level are represented by a lowercase string. For example, $S = "xaabxcbc"$ indicates there are 8 levels. Levels 1 and 5 can use all types of cars. Levels 2 and 3 cannot use car `A`, levels 4 and 7 cannot use car `B`, and levels 6 and 8 cannot use car `C`.
There are also $m$ constraints of the form $i, h_i, j, h_j$, meaning that if car $h_i$ is used in level $i$, then car $h_j$ must be used in level $j$.
The task is to find a way to use cars for $n$ levels. If multiple solutions exist, any solution can be printed. If no solution is possible, print `-1`.
### Input
- The first line consists of two non-negative integers $n,d$, where $d$ is the maximum number of levels with the map `x`.
- The second line is the string $S$ representing the maps for each level.
- The third line is an integer $m$ indicating the number of constraints.
- The next $m$ lines, each containing four integers $i, h_i, j, h_j$.
### Output
- Print a string of length $n$ representing the types of cars to be used. If no solution exists, print `-1`.
### Example
Input:
```
3 1
xcc
1
1 A 2 B
```
Output:
```
ABA
```
### Constraints
Test Point Number |
n |
d |
m |
Other Properties |
1 |
$ \leq 2 $ |
0 |
$ \leq 4 $ |
None |
2 |
$ \leq n $ |
3 |
$ \leq 5 $ |
0 |
$ \leq 10 $ |
4 |
$ \leq n $ |
5 |
$ \leq 10 $ |
0 |
$ \leq 20 $ |
6 |
$ \leq 8 $ |
7 |
$ \leq 20 $ |
0 |
$ \leq 40 $ |
S contains only c |
8 |
None |
9 |
$ \leq 8 $ |
S contains only x or c |
10 |
None |
11 |
$ \leq 100 $ |
0 |
$ \leq 200 $ |
S contains only c |
12 |
None |
13 |
$ \leq 8 $ |
S contains only x or c |
14 |
None |
15 |
$ \leq 5 \times 10^3 $ |
0 |
$ \leq 10^4 $ |
16 |
$ \leq 8 $ |
S contains only x or c |
17 |
None |
18 |
$ \leq 5 \times 10^4 $ |
0 |
$ \leq 10^5 $ |
19 |
$ \leq 8 $ |
S contains only x or c |
20 |
None |
Topic
Graph
Rating
2200
Solution (0)
Solution