Under construction

Still being built. Things may change

Game Scheduling

Time limit3sMemory limit512 MB

Summary
Given n players per team and m teams, build a round schedule where each player plays everyone outside their own team and has at most one bye.
Level

Hard8 of 10

Topics
Graph, Greedy, Implementation
Solved
No attempts yet

Problem

In a tournament with mm teams, each team consisting of nn players, construct a playing schedule so that each player is paired up against all players in all teams except their own. That is, each player should play (m−1)n(m-1)n games.

The playing schedule is divided into rounds. A player can play at most one game per round. If a player does not play a game in a round, that player is said to have a bye in that round.

Write a program that constructs a playing schedule so that no player has a bye in more than 1 round. In other words, the total number of rounds should be no more than (m−1)n+1(m-1)n+1.

The order of the rounds and games, and which side is home and away in a game, does not matter.

Input

The input consists of a single line with two integers nn and mm (1≤n≤251 \le n \le 25, 2≤m≤252 \le m \le 25, n×m≤100n \times m \le 100), the number of players in a team and the total number of teams, respectively.

Output

Output one line per round in the playing schedule. Each line contains a space-separated list of games. A game is written as <player>-<player>. The players in the first team are named A1, A2, ..., An, the players in the second team B1, B2, ..., Bn, and so on.

Examples3

  1. Example 1

    Input
    3 2
    Expected output
    A1-B2 B1-A2 A3-B3
A2-B3 B2-A3 A1-B1
A3-B1 B3-A1 A2-B2

  2. Example 2

    Input
    2 3
    Expected output
    A1-B1 A2-C2 B2-C1
A1-C1 A2-B1 B2-C2
A1-B2 A2-C1 B1-C2
A1-C2 A2-B2 B1-C1

  3. Example 3

    Input
    1 5
    Expected output
    B1-E1 C1-D1
C1-A1 D1-E1
D1-B1 E1-A1
E1-C1 A1-B1
A1-D1 B1-C1