The simplest (but non-qualifying) solution

simulate this circuit – Schematic created using CircuitLab
Figure 1. By changing the switch type the problem becomes simple.
AC solution

simulate this circuit
Figure 2. By not changing the switch type the problem is more difficult!
Gray code sequence
A trick to looking at this solution is to write the truth table in Gray code rather than a normal binary sequence. This is important because only one switch will be changed at a time and it will be easy to see the lamp status change.
Table 1. Switch combinations in Gray code sequence.
SW1 SW2 L1 L2
-------------------
0 0 ON --
1 0 -- ON
1 1 ON --
0 1 -- ON
0 0 ON -- <-- First step repeated
With the Gray code it is easy to see that every one-switch change results in a reversal of the lights' status.
DC solution

simulate this circuit
Figure 3. The DC version.
Binary sequence
Here is the pattern in binary code sequence.
Table 2. Switch combinations in binary code sequence.
SW1 SW2 L1 L2
-------------------
0 0 ON --
1 0 -- ON
0 1 -- ON
1 1 ON --
0 0 ON -- <-- First step repeated
Note how much more difficult it is to visually verify that the requirements have been met.